8 · Recurrences: recursion trees & guess-and-verify

In one sentence

A recurrence describes running time in terms of smaller inputs, e.g. $T(n) = 2T(n/2) + n$ . Solve it by drawing the recursion tree, adding up the cost of each level, and, when asked, proving the guess by induction (the substitution method).

Everyday analogy

A company org chart. The CEO does $f(n)$ work personally and hands the rest to $a$ managers, each handling a $1/b$ share. They do the same with their teams, and so on down to the interns (the base cases). The company's total work = the sum over every level of the chart. Ask yourself: is most of the work done at the top, at the bottom, or spread evenly?

Key tools

Recursion-tree level table for $T(n) = a\,T(n/b) + f(n)$ :

Level $i$	# nodes	Size of each	Cost per node	Level total
0	1	$n$	$f(n)$	$f(n)$
1	$a$	$n/b$	$f(n/b)$	$a\,f(n/b)$
$i$	$a^i$	$n/b^i$	$f(n/b^i)$	$a^i f(n/b^i)$
last ( $i = \log_b n$ )	$a^{\log_b n} = n^{\log_b a}$	1	$\Theta(1)$	$\Theta(n^{\log_b a})$

Then look at the level totals:

Level totals…	Then $T(n)$ is…	Example
equal on every level	level cost × number of levels	$2T(n/2) + n \Rightarrow \Theta(n\log n)$
shrinking geometrically going down	dominated by the root	$2T(n/2) + n^2 \Rightarrow \Theta(n^2)$
growing geometrically going down	dominated by the leaves, $\Theta(n^{\log_b a})$	$4T(n/2) + n \Rightarrow \Theta(n^2)$

Other methods

Expansion (iteration): substitute the recurrence into itself a few times, spot the pattern, then sum. Best for $T(n) = T(n-1) + \dots$
Substitution (guess and verify): guess the answer (often from the tree), then prove it by induction (Topic 2).
Master theorem (CLRS §4.5): a shortcut for the three rows above. Not in the slides yet, so use it to check answers unless your instructor allows it.

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

Level	nodes	size	level total
0	1	$n$	$n$
1	2	$n/2$	$n$
2	4	$n/4$	$n$
$\log_2 n$	$n$	1	$n$

Equal levels: $n \times (\log_2 n + 1)$ levels, so $\Theta(n\log n)$ .

$T(n) = 2T(n/2) + n^2$ : the root dominates

Level	nodes	size	level total
0	1	$n$	$n^2$
1	2	$n/2$	$2\cdot\frac{n^2}{4} = \frac{n^2}{2}$
2	4	$n/4$	$\frac{n^2}{4}$

The totals halve each level: $n^2(1 + \frac12 + \frac14 + \dots) \le 2n^2$ , so $\Theta(n^2)$ .

$T(n) = 4T(n/2) + n$ : the leaves dominate

Level totals $n, 2n, 4n, \dots$ double going down. The leaves: $4^{\log_2 n} = n^{\log_2 4} = n^2$ , so $\Theta(n^2)$ .

Common mistakes

Writing the level total as $f(n/b^i)$ and forgetting to multiply by the number of nodes $a^i$ .
Wrong number of levels: it's $\log_b n$ (where the size reaches 1), not $\log_a n$ .
Forgetting the leaves' cost $n^{\log_b a}$ when levels grow.
In substitution: proving $T(n) \le cn\log n + n$ and calling it done. You must get back to exactly $\le cn\log n$ with the same $c$ .
Using $\log$ rules wrongly: $\log_2(n/2) = \log_2 n - 1$ , not $\frac{\log_2 n}{2}$ .

Mastery check

Solve without hints, then explain level by level

(a) Solve $T(n) = 3T(n/3) + n$ with a recursion tree (build the full level table).

(b) Solve $T(n) = 2T(n/2) + n^2$ and say why the root dominates.

Your mastery check

Not started

Solve the problem above with no hints, close the page and explain it out loud. Tick each step honestly.

Solved the mastery check with no hints

Said it in one sentence

Explained it with my own analogy

Walked through the steps of my own hand trace

Explained why it is correct / how fast it is

Named a trap a beginner would fall into

Status

Tick all six steps to unlock “Mastered”.

Which study mode worked for you?

Saved in this browser onlySee all my progress →

See it move

VisuAlgo: Recursion tree: enter a recursive function and watch the tree.

References

08 Divide & Conquer, Recurrences: Slides 25–29 (merge sort recurrence and full recursion tree), 30–33 (techniques, recursion-tree method), 34–42 (worked recursion-tree examples, including an uneven split).
Supplementary Notes: Proof techniques p. 6 (verifying a recurrence's closed form by induction).
CLRS 4e §4.3 (substitution method), §4.4 (recursion-tree method), §4.5 (master method, a preview), Appendix A (geometric series).

8 · Recurrences: recursion trees & guess-and-verify

Everyday analogyCopy Anchor Link

Key toolsCopy Anchor Link

Common mistakesCopy Anchor Link

Mastery checkCopy Anchor Link

✅ Answers

See it moveCopy Anchor Link