Elementary Introduction to Recurrences for COSC 311

Here are a few common recurrences

Recurrence Example big Oh
T(n) = T(n/2) + 1 binary search of an array O(log n)
T(n) = 2 * T(n/2) + 1 postorder binary tree traversal O(n log n)
T(n) = T(n-1) + 1 count elements in a linked list O(n)
T(n) = T(n-1) + n insertion sort O(n2)
T(n) = 2 * T(n/2) + n merge sort O(n log n)

Solving Recurrences

There is no one way to solve recurrences. Often, especially for the recurrences above, it is possible to intuit a solution. To prove the intuited solution is correct, use an inductive proof (don't appeal to asymptotic bounds -- just use "g(n)") in the induction.

Here's one approach to intuiting a solution to T(n) = 2 * T(n/2) + O(n). Assume the base case is T(1) = 1.

Stepwise, substitute the solution for each T(k), k = n, n/2, n/4, ... until you see a pattern. In this case, we are starting from k = n and going down. Other times, you may want to start from k = 1 and go up.

T(n)  = 2 * T(n/2) + n
   = 2 * ( 2 T(n/4) + n/2) + n  = 4 T(n/4) + 2 n
   = 4 * ( 2 T(n/8) + n/4) + 2 n  = 8 T(n/8) + 3 n
   = 8 * ( 2 T(n/16) + n/8) + 3 n  = 16 T(n/16) + 4 n

Look at the pattern that has developed: T(n) = 2k T(n/2k) + k n

We can only work our way down to the base case where T(1) = 1

To end the expansion, we want T(1) on the right hand side. From the pattern we have detected, the right hand side term for T is T(n/2k).
So, what is n when n/2k = 1?
Well, n = 2k.

And what is k when n/2k = 1?
Well, 2k = n, or k = log n.

Substitute log n for k in T(n) = 2k T(n/2k) + k n .

T(n) = 2k T(n/2k) + k n
gives T(n) = n T(1) + (log n) n
Recall T(1) = 1 T(n) = n + n log n and so (!) T(n) = O (n log n)

The other recurrences can have solutions intuited in similar ways, by counting up from k = 1 or by counting down from k = n. Find the pattern. Solve for n interms of k (or k in terms of n), and bob's your uncle (we hope!).