Recursion Trees

What are recursion trees?

Recursion trees are a simple, general, pictorial tool for solving divide-and-conquer recurrences. A recursion tree is a rooted tree with one node for each recursive subproblem. The value of each node is the amount of time spent on the corresponding subproblem, excluding recursive calls. Thus, the overall running time of the algorithm is the sum of the values of all nodes in the tree.

To make this idea more concrete, imagine a divide-and-conquer algorithm that spends $O( f (n))$ time on non-recursive work and then makes $r$ recursive calls, each on a problem of size $n/c$. Up to constant factors (which we can hide in the $O( )$ notation), the running time of this algorithm is governed by the recurrence

$$T (n) = r T (n/c) + f (n).$$

The root of the recursion tree for $T(n)$ has value $f(n)$ and $r$ children, each of which is the root of a (recursively defined) recursion tree for $T(n/c)$. Equivalently, a recursion tree is a complete $r$-ary tree where each node at depth $d$ contains the value $f (n/c^d )$. (Feel free to assume that $n$ is an integer power of c so that $n/c^d$ is always an integer, although, in fact, this doesn’t matter.)

In practice, we recommend drawing out the first two or three levels of the tree, as in the figure below.

The leaves of the recursion tree correspond to the base case(s) of the recurrence. Because we’re only looking for asymptotic bounds, the precise base case doesn’t actually matter; we can safely assume $T(n) = 1$ for all $n ≤ n_0$, where $n_0$ is an arbitrary positive constant. In particular, we can choose whatever value of $n_0$ is most convenient for our analysis. For this example, we’ll choose $n_0 = 1$.

Now $T(n)$ is the sum of all values in the recursion tree; we can evaluate this sum by considering the tree level by level. For each integer $i$, the $i$th level of the tree has exactly $r^i$ nodes, each with value $f (n/ci)$ ...