Foundations‎ > ‎Algorithms‎ > ‎

Recurrence

An algorithm that contains a call to itself is called a recursive algorithm. Usually seen in "Divide and Conquer" type algorithms, the running time of recursive algorithms can often be described by a recurrence. A recurrence is an equation or inequality that describes a function in terms of its values on smaller inputs. There are three methods for solving recurrences to obtain asymptotic bounds on the recursive algorithms they describe. These methods are as follows.

- The substitution method -

Using the substitution method, one needs to follow the following two steps in order to solve recurrences.

1. Guess the form of the solution.
2. Use mathematical induction to show the guess in step 1 works.

- The iteration/recursion-tree method -

In this method, one repeats substituting t(n) with what t(n) equates to until a pattern is discovered which ends with t(constant), as the input of the function gets smaller with every step.

Example:
t(n) = 2t(n/2) + n2 = 2(2t(n/4) + n2) + n2 = 2(2(2t(n/8) + n2) + n2) + n2 . . . t(n) ≤ n2 (1 + 1/2 + 1/4 + ... = 2n2 = Θ(n2)

Alternatively one can draw a recursion tree which is very similar to writing out the iterations
cn2 / \ / \ t(n/2) t(n/2) cn2 / \ / \ c(n/2)2 c(n/2)2 / \ / \ / \ / \ c(n/4)2c(n/4)2 c(n/4)2 c(n/4)2 . . .
The height of this tree is lg n, Hence
 
t(n) ≤ n2 (1 + 1/2 + 1/4 + ... = 2n2 = Θ(n2)

Normally this method is used for producing a good guess for the substitution method, but if you are careful with the details when doing the iteration or drawing the tree, you don't need to prove your answer with substitution.

- The master method -

Let a ≥ 1, b > 1. Let t(n) = at(n/b) + f(n). t(n) = Θ(1). then t(n) can be bounded asymptotically as follows:

1. if f(n) = O(nlogba-ε) for some constant ε > 0, then t(n) = Θ(nlogba).
2. if f(n) = Θ(nlogba), then t(n) = Θ(nlogbalg n).
3. if f(n) = Ω(nlogba+ε) for some constant ε > 0, and if af(n/b) ≤ cf(n) for some constant c1, and n sufficiently large, then t(n) = Θ(f(n)).


Note that not all recurrences can be solved using the master method. For the ones that don't apply to any of the above cases, you have to use either the iteration/recursion-tree method or the substitution method.

Recurrence Algorithm Big-Oh Solution
T(n) = T(n/2) + O(1) Binary Search O(log n)
T(n) = T(n-1) + O(1) Sequential Search O(n)
T(n) = 2 T(n/2) + O(1) tree traversal O(n)
T(n) = T(n-1) + O(n) Selection Sort (other n2 sorts) O(n2)
T(n) = 2 T(n/2) + O(n) Mergesort (average case Quicksort) O(n log n)