Today we'll do what LevitinBook calls DecreaseByConstantFactor and DecreaseByVariableFactor algorithms. These are algorithms whose recurrence is of the form

• T(n) = T(n/c) + f(n)

or

• T(n) = T(k) + f(n)

where k may depend on any number of things.

1. Examples

• Russian peasant's algorithm (RussianPeasantsAlgorithm).

• Euclid's GCD (EuclidsAlgorithm)

• Binary search (BinarySearch)

Egyptian fractions were discussed at some length for no good reason. If you want to find out more about them, there is no more comprehensive resource that David Eppstein's Egyptian fractions web page. You do not need to know about these for the course.

/2004-01-13   /2004-01-15   /2004-01-20   /2004-01-22   /2004-01-27   /2004-01-29   /2004-02-03   /2004-02-05   /2004-02-10   /2004-02-12   /2004-02-17   /2004-02-19   /2004-02-24   /2004-03-02   /2004-03-04   /2004-03-23   /2004-03-25   /2004-03-30   /2004-04-01   /2004-04-06   /2004-04-08   /2004-04-13   /2004-04-15   /2004-04-20   /2004-04-22