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.