PineWikiA 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) = Sigmai=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.
