A decrease-by-a-constant algorithm typically processes its input one element at a time, accumulating a solution as it goes. Such algorithms are often naturally written using iteration rather than recursion.

1. Typical recurrence

The typical recurrence for an algorithm in this class is

• T(n) = T(n-1) + f(n)

which has the solution (see SolvingSums)

• T(n) = Sigma_{i=1 to n} f(n) + T(0).

For most reasonable functions f, this will just be Theta(n f(n)). So the key to getting a fast decrease-by-a-constant algorithm is to keep the cost of each iteration small.

2. Examples

• InsertionSort

• SelectionSort

• DepthFirstSearch

• BreadthFirstSearch

• TopologicalSort

---

CategoryAlgorithmNotes