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 the 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.