15.1 Recursion Trees

Problem

You are given a recursive algorithm and want to determine its time complexity. The implementation repeatedly divides a problem into smaller subproblems, performs some work at each level of recursion, and eventually reaches a base case.

A recurrence such as

$$ T(n) = 2T\left(\frac{n}{2}\right) + n $$

describes the running time, but the growth rate is not immediately obvious.

How can you visualize the work performed by the recursion and derive the total running time?

Solution

Build a recursion tree.

A recursion tree expands the recurrence into levels. Each node represents a recursive call, and the value stored in the node represents the non-recursive work performed by that call.

Consider:

$$ T(n) = 2T\left(\frac{n}{2}\right) + n $$

The root performs (n) units of work.

It creates two subproblems of size (n/2).

Each child performs:

$$ \frac{n}{2} $$

units of work.

The first few levels look like:

Level	Number of Nodes	Work per Node	Total Work
0	1	n	n
1	2	n/2	n
2	4	n/4	n
3	8	n/8	n
k	(2^k)	(n/2^k)	n

Every level contributes exactly (n).

The recursion stops when:

$$ \frac{n}{2^h}=1 $$

which gives:

$$ h=\log_2 n $$

levels.

Since each level contributes (n) work:

$$ T(n)=n+n+n+\cdots+n $$

for (\log n) levels.

Therefore:

$$ T(n)=\Theta(n\log n) $$

Visualizing the Tree

The recursion tree can be drawn as:

                    n
               /         \\n            n/2           n/2
          /    \         /    \\n       n/4    n/4     n/4    n/4
      /  \    /  \   /  \    /  \\n     ...

The important observation is that the total work across any horizontal level remains constant.

Instead of analyzing thousands of recursive calls individually, we analyze a handful of levels.

Recipe: Constructing a Recursion Tree

Given a recurrence:

$$ T(n)=aT\left(\frac{n}{b}\right)+f(n) $$

follow these steps.

Step 1: Identify Branching Factor

Determine how many recursive calls are created.

$$ a $$

is the number of children per node.

Step 2: Determine Subproblem Size

Each child receives:

$$ \frac{n}{b} $$

elements.

Step 3: Compute Work Per Node

Ignore recursive calls and focus only on local work.

This is:

$$ f(n) $$

Step 4: Compute Work Per Level

Multiply:

$$ (\text{nodes}) \times (\text{work per node}) $$

at each depth.

Step 5: Determine Tree Height

Solve:

$$ \frac{n}{b^h}=1 $$

which gives:

$$ h=\log_b n $$

Step 6: Sum All Levels

Add contributions from every level.

This often reveals a pattern immediately.

Example: Binary Search

Binary search satisfies:

$$ T(n)=T\left(\frac{n}{2}\right)+1 $$

The tree has one node at every level.

Level	Work
0	1
1	1
2	1
3	1
...	...

Height:

$$ \log_2 n $$

Total work:

$$ 1+1+\cdots+1 $$

for (\log n) levels.

Thus:

$$ T(n)=\Theta(\log n) $$

Example: Merge Sort

Merge sort satisfies:

$$ T(n)=2T\left(\frac{n}{2}\right)+n $$

The recursion tree shows:

Level	Total Work
0	n
1	n
2	n
3	n
...	...

Height:

$$ \log n $$

Total:

$$ n\log n $$

Hence:

$$ T(n)=\Theta(n\log n) $$

Example: Naive Fibonacci

The recursive Fibonacci algorithm:

fib(n)
    fib(n-1)
    fib(n-2)

generates:

$$ T(n)=T(n-1)+T(n-2)+1 $$

The recursion tree expands exponentially.

Each level grows rapidly, producing nearly twice as many calls as the previous level.

The total node count becomes approximately:

$$ \Theta(\varphi^n) $$

where (\varphi) is the golden ratio.

The recursion tree immediately reveals why naive Fibonacci becomes impractical even for moderate values of (n).

Recognizing Common Patterns

Constant Work Per Level

$$ T(n)=2T(n/2)+n $$

Every level contributes the same amount.

Result:

$$ \Theta(n\log n) $$

Increasing Work Toward Leaves

$$ T(n)=4T(n/2)+n $$

At depth (k):

$$ 4^k \cdot \frac{n}{2^k} = n2^k $$

Work increases as we descend.

Leaf work dominates.

Result:

$$ \Theta(n^2) $$

Decreasing Work Toward Leaves

$$ T(n)=T(n/2)+n $$

Level contributions:

$$ n,\frac{n}{2},\frac{n}{4},... $$

Geometric series:

$$ 2n $$

Result:

$$ \Theta(n) $$

Common Mistakes

Ignoring Leaf Costs

Leaves may collectively contribute substantial work.

Always calculate leaf contribution separately.

Counting Levels Incorrectly

For:

$$ T(n)=T(n/2) $$

the height is:

$$ \log_2 n $$

not (n/2).

Summing Node Costs Incorrectly

Work per node and work per level are different quantities.

Many mistakes occur because these are confused.

Forgetting Base Cases

Recursion trees stop at the base case.

Infinite trees correspond to invalid recurrences.

Discussion

Recursion trees provide intuition that purely algebraic techniques often hide. They expose where work accumulates, reveal whether internal nodes or leaves dominate the running time, and frequently allow a complexity estimate before formal analysis begins.

Later in this chapter, the Master Theorem will automate many of these calculations. Even when that theorem applies, experienced algorithm designers still sketch recursion trees because they reveal structural properties that formulas alone cannot show. Understanding the shape of a recursion tree is often the fastest way to understand the behavior of a divide-and-conquer algorithm.