DecreaseAndConquer - PineWiki

General pattern for algorithms whose recurrence includes only one recursive term. Special cases are:

DecreaseByConstant: T(n) = T(n-c) + f(n).
DecreaseByConstantFactor: T(n) = T(n/c) + f(n).
- BinarySearch
DecreaseByVariableFactor: T(n) = T(k) + f(n), where k may be a RandomVariable or depend on the problem instance.
- QuickSelect
- Some operations on BinaryTrees.

DecreaseAndConquer (last edited 2007-12-25 23:42:28 by localhost)