Recursion Trees and Substitution

You have a recurrence like T(n) = 2\,T(n/2) + n. Now what? A recurrence is a promise that never quite pays out — it always defers to a smaller version of itself. To turn it into an honest closed form like \Theta(n\log n) you need a technique. This page gives you two, and they work as a team: the recursion-tree method to discover the answer by drawing the computation and adding it up, and the substitution method to prove that answer rigorously by induction.

The division of labour is deliberate. Trees are visual and fast but easy to fudge — a hand-wave in the geometric series and you are off by a factor. Substitution is airtight but needs a guess to start from. So: draw the tree to guess, then substitute to prove. Guess-then-verify is the whole game.

The recursion-tree method

A recursion tree makes the recurrence's own hidden structure visible. Each node is one subproblem, labelled with the non-recursive work it does; its children are the subproblems it spawns. Then the total running time is simply the sum of every node's label — and the trick is to sum it level by level, because within a level the arithmetic is easy.

Cost per node. A node handling a subproblem of size m is labelled f(m) — the divide-and-combine work, not including its children.
Nodes per level. With a children each, level i has a^i nodes, each of size n/b^i.
Cost per level. Multiply: a^i \cdot f(n/b^i). This is usually a clean expression in i.
Number of levels. The size hits the base case (1) when n/b^i = 1, i.e. at depth i = \log_b n.
Total. Sum the level costs from i = 0 to \log_b n — almost always a geometric series.

The geometric series is where all the action is. If the level costs grow geometrically down the tree, the bottom level dominates; if they shrink, the root dominates; if they stay constant, every level contributes equally and you get an extra \log n factor. Those three regimes are exactly the three cases of the master theorem — the recursion tree is where that theorem comes from.

Worked example: T(n) = 2\,T(n/2) + n

Reveal the tree level by level. Each node's label is its own work; watch the right-hand column, which tallies the total work on each level.

Every level costs the same: level i has 2^i nodes each doing n/2^i work, and 2^i \cdot (n/2^i) = n — the factors cancel exactly. There are \log_2 n + 1 levels, so

T(n) = \sum_{i=0}^{\log_2 n} n = n\,(\log_2 n + 1) = \Theta(n\log n).

This is the "constant level cost" regime — the signature of merge sort. Because the work is spread evenly across \log n levels, neither the root nor the leaves dominate; the whole tree matters, and the \log n factor is the number of levels made visible.

Worked example: T(n) = 3\,T(n/4) + n^2

Now the level costs are not constant. Level i has 3^i nodes, each of size n/4^i doing (n/4^i)^2 = n^2/16^i work, so the level cost is

3^i \cdot \frac{n^2}{16^i} = \left(\frac{3}{16}\right)^{i} n^2.

The ratio 3/16 < 1, so the level costs shrink geometrically as you descend — the root's n^2 already dominates. Summing the decreasing geometric series over all levels stays within a constant factor of its first term:

T(n) = \sum_{i=0}^{\log_4 n} \left(\tfrac{3}{16}\right)^{i} n^2 \le n^2 \sum_{i=0}^{\infty} \left(\tfrac{3}{16}\right)^{i} = n^2 \cdot \frac{1}{1 - 3/16} = \frac{16}{13}\,n^2 = \Theta(n^2).

A decreasing geometric series is a constant times its largest term — so the root wins and T(n) = \Theta(n^2). Contrast merge sort, where the ratio was exactly 1 and no single level won. The ratio of consecutive level costs is the entire story.

The substitution method

The tree suggested \Theta(n\log n); substitution proves it. You guess a bound, then verify it by induction on n — assume the bound for all smaller inputs, substitute that assumption into the recurrence, and show the bound survives for n.

Let's prove T(n) \le c\,n\log_2 n for the merge-sort recurrence T(n) = 2\,T(n/2) + n. Inductive step: assume the bound holds for n/2, so T(n/2) \le c\,(n/2)\log_2(n/2). Substitute:

\begin{aligned} T(n) &= 2\,T(n/2) + n \\ &\le 2\Big(c\,\tfrac{n}{2}\log_2\tfrac{n}{2}\Big) + n = c\,n\log_2\tfrac{n}{2} + n \\ &= c\,n(\log_2 n - 1) + n = c\,n\log_2 n - c\,n + n \\ &= c\,n\log_2 n - (c - 1)\,n \;\le\; c\,n\log_2 n \quad\text{whenever } c \ge 1. \end{aligned}

The final line closes the induction: the leftover -(c-1)n is \le 0 as long as c \ge 1, so T(n) \le c\,n\log_2 n exactly as guessed. Pick any c \ge 1 big enough to also cover the base case, and the bound holds for all n: T(n) = O(n\log n). A symmetric argument with \ge gives the matching \Omega, hence \Theta(n\log n).

A beginner's proof often stalls at T(n) \le c\,n\log_2 n + n and declares victory — "that's O(n\log n), isn't it?" No. Induction is unforgiving: to prove T(n) \le c\,n\log_2 n you must reach exactly that expression, with no +n hanging off the end, or the same slack reappears at every level and accumulates to something bigger. The fix here is that the algebra genuinely produces c\,n\log_2 n - (c-1)n, and the negative term absorbs the stray +n. When it doesn't cancel so kindly, the classic trick is to strengthen the guess by subtracting a lower-order term — prove T(n) \le c\,n - d instead of c\,n — giving the induction extra room. Strengthening the hypothesis to make it easier to prove is one of induction's great counterintuitive moves.

Here is a proof that looks correct and is not. Claim: T(n) = 2\,T(n/2) + n is O(n). "Proof": assume T(n/2) \le c\,(n/2), then T(n) \le 2\cdot c(n/2) + n = cn + n = (c+1)n = O(n). The fatal flaw: the constant grew from c to c+1. To satisfy the definition of O(n) you must land back on the same c\,n you assumed, and (c+1)n \not\le cn. Because O(n) hides the constant, the leak is invisible unless you write the constant out explicitly. Always name your constant and demand the identical one back at the end — a substitution proof that lets the constant drift is proving nothing at all.