Recurrences

A loop’s cost is a sum. A recursive function’s cost is harder, because it calls itself. Its cost is written as an equation called a recurrence, and this lesson shows two ways to solve one.

Cost described by itself

Here is merge sort in outline. SORT-2 builds it in full.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])        # T(n/2)
    right = merge_sort(a[mid:])       # T(n/2)
    return merge(left, right)         # about n steps

Let T(n) be the number of steps for a list of n values. The function makes two calls on half the list, and does about n steps of its own (the slices and the merge). So:

The second part, T(1) = 1, is the base case: a list of one value costs a constant amount. A recurrence is not an answer yet. We want a plain formula for T(n).

Unrolling

One way is to replace T by its own definition again and again, and look for a pattern. Take n to be a power of 2, so the halves are always whole:

T(n) = 2T(n/2) + n
     = 2[2T(n/4) + n/2] + n  = 4T(n/4) + 2n
     = 4[2T(n/8) + n/4] + 2n = 8T(n/8) + 3n
     ...
     = 2^k T(n/2^k) + k·n      # 2^k: k twos multiplied together

Here 2^k means 2ᵏ, k twos multiplied together. The halving stops when n/2ᵏ = 1, which is when k = log₂ n. Put that in: T(n) = n × T(1) + n log₂ n = n + n log₂ n. So T(n) is Θ(n log n).

A pattern spotted this way is a guess. To be sure, prove it by induction (CORR-3): assume the formula for n/2, and show it holds for n.

The recursion tree

A picture often makes the pattern obvious. Draw each call as a box, with the calls it makes below it. Write next to each box the work it does itself, not counting its calls. Then add up the tree one level at a time.

The two trees have the same work at the top, n, but very different totals. Halving gives log₂ n levels. Shrinking by one gives n levels. Most of the difference between fast and slow divide-and-conquer comes down to this.

Four recurrences to know

Lesson 6 gives a shortcut for the first two rows and many more like them.