Recursion Trees

Explore the various properties of recursion trees, such as height and the number of nodes.

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))O( f (n)) time on non-recursive work and then makes rr recursive calls, each on a problem of size n/cn/c. Up to constant factors (which we can hide in the O()O( ) notation), the running time of this algorithm is governed by the recurrence

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

The root of the recursion tree for T(n)T(n) has value f(n)f(n) and rr children, each of which is the root of a (recursively defined) recursion tree for T(n/c)T(n/c). Equivalently, a recursion tree is a complete rr-ary tree where each node at depth dd contains the value f(n/cd)f (n/c^d ). (Feel free to assume that nn is an integer power of c so that n/cdn/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.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy