Recurrences

A recursive call on n does n units of work and calls itself twice on n/2. How much work is that in all? Add it up one level at a time.

A cost in terms of smaller costs

A recursive function’s cost depends on the cost of its own calls. Write T(n) for the cost on an input of size n, and read the recurrence straight off the code. Merge sort sorts two halves and merges them in about n steps, so

Binary search does a constant amount of work and continues in one half: T(n) = T(n/2) + 1. Each also needs a base case, a constant cost for the smallest inputs, here T(1) = 1. A recurrence is solved when T(n) is written without T on the right, exactly or as a Θ bound.

The method

Recursion trees

Draw every call as a node, under the call that made it, and write in each node the work that call does outside its own recursive calls. For T(n) = aT(n/b) + f(n), the root does f(n); its a children do f(n/b) each; their a² children do f(n/b²) each; and so on until the size reaches 1, after $\log_b n$ levels of dividing by b. The cost is the sum of every node, and the easiest way to add the nodes is one level at a time.

Level k has $a^k$ calls of size $n/b^k$. The tree’s leaves, at level $\log_b n$, number

since both sides have the same logarithm to base b, $(\log_b n)(\log_b a)$.

For f(n) = n and b = 2, as in the clip, level k does $a^k \cdot n/2^k = n\,(a/2)^k$. With n = 16:

The level sums form a geometric series with ratio a/2. When the ratio is below 1 the series is dominated by its first term, the root. When it is 1 every level counts the same, and there are log₂ n + 1 of them. When it is above 1 the last term dominates: the leaves. The totals are exactly $2n-1$, $n\log_2 n + n$, $3n^{\log_2 3} - 2n$ and $2n^2 - n$.

Substitution

A recursion tree suggests an answer; substitution proves it. Guess the form of the answer, then show by induction that it satisfies the recurrence. For merge sort with T(1) = 1 and n a power of 2, guess T(n) = n log₂ n + n. It holds at n = 1, since 1·0 + 1 = 1. If it holds at n/2, then

so it holds at n. At n = 16 it gives 80, the clip’s total. For a Θ bound the guess can carry unknown constants, T(n) ≤ c·n log₂ n, and the induction then shows which c works.

The master theorem

The three shapes of the clip are the three cases of the master theorem. Let a ≥ 1 and b > 1 be constants, and let

with d ≥ 0 a constant and T(n) constant for small n; n/b may be rounded up or down. Then

Comparing a with $b^d$ is comparing $\log_b a$ with d: the exponent of the number of leaves against the exponent of the root’s work. Level k does $a^k (n/b^k)^d = n^d (a/b^d)^k$, the same geometric series, with ratio $a/b^d$.

The theorem also has a form for any f(n), not only powers of n. With $p = \log_b a$: if $f(n) = O(n^{p-\varepsilon})$ for some ε > 0, then $T(n) = \Theta(n^p)$; if $f(n) = \Theta(n^p)$, then $T(n) = \Theta(n^p \log n)$; and if $f(n) = \Omega(n^{p+\varepsilon})$ for some ε > 0 and $a\,f(n/b) \le c\,f(n)$ for some constant c < 1 and all large n, then $T(n) = \Theta(f(n))$.

What it does not cover

The theorem needs a problem divided by a constant factor into a fixed number of parts. The Tower of Hanoi makes its problem smaller by one, not by a factor: M(n) = 2M(n − 1) + 1, whose solution is 2ⁿ − 1, exponential. The tree is a full binary tree n levels deep, and its levels sum to 1, 2, 4, …, 2ⁿ⁻¹.

It also misses work that falls between the cases. For T(n) = 2T(n/2) + n log₂ n, f is larger than $n^{\log_2 2} = n$, but not by a power of n, so no case applies. The tree still works: level k does $n\log_2(n/2^k) = n(\log_2 n - k)$, and adding the levels k = 0 to L − 1, with L = log₂ n, gives nL(L + 1)/2. The n leaves add n more, one each, so exactly T(n) = nL(L + 1)/2 + n, which is $\Theta(n \log^2 n)$.

Worked example

Binary search and fast powers. T(n) = T(n/2) + 1: a = 1, b = 2, d = 0, and b^d = 1 = a, the middle case: Θ(log n). Fast powers, which square and halve the exponent, have the same recurrence.

Merge sort. T(n) = 2T(n/2) + n: a = 2 = 2¹, the middle case again: Θ(n log n).

Three products instead of four. Multiplying polynomials by halves needs four half-size products, T(n) = 4T(n/2) + n, which is Θ(n²): no better than the double loop. The split that makes do with three gives T(n) = 3T(n/2) + n: a = 3 > 2, so $\Theta(n^{\log_2 3})$, about $n^{1.585}$. At n = 1,024 = 2¹⁰ the tree has 3¹⁰ = 59,049 leaves, each a product of two single coefficients, against 4¹⁰ = 1,048,576 with four products. More branches do not mean exponential time: three branches on half the size grow more slowly than n².

Not covered. The Tower of Hanoi’s M(n) = 2M(n − 1) + 1 = 2ⁿ − 1, solved by its tree, not by the theorem.

Two checks. What is T(n) = 2T(n/2) + n²? (Θ(n²): a = 2 < 2² = 4, so the root dominates.) How many leaves has the a = 3 tree at n = 16? (3⁴ = 81.)

Where it’s used

Analysing any divide-and-conquer algorithm: sorting, as in merge sort and quicksort’s best case; searching; and fast multiplication.

The FFT, whose recurrence is T(n) = 2T(n/2) + n, the merge sort recurrence, and so Θ(n log n): the FFT in the signal processing course.

Reference card