The Recursion Tree and the Master Theorem

The idea: a recurrence is a tree of costs

A divide-and-conquer algorithm splits its input, calls itself on the parts and then does some work of its own to split or combine. Its running time is written as a recurrence: T(n) = a·T(n/b) + f(n). Read it as a picture. Draw the first call as a box. It makes a calls, each on an input b times smaller, so it gets a children. Each child does the same, down to inputs of size 1. That picture is the recursion tree. Write each box's own work f(size) next to it, add up each level, and add up the levels. The sum is T(n).

Reading a, b and f(n)

• a is the number of recursive calls per call: the number of children of each box.
• b is how much smaller each call's input is: the size drops from n to n/b to n/b² as you go down.
• f(n) is the work a call does outside its recursive calls: merging in merge sort, one comparison in binary search.

The size reaches 1 after log_b n halvings, so the tree has log_b n + 1 levels. The canvas uses n = 16 and b = 2: levels 0 to 4.

Sum the work per level

Level i has aⁱ calls, each on size n/bⁱ, so the level costs aⁱ · f(n/bⁱ). The bottom level has a^{log_b n} = n^{log_b a} leaves, each costing T(1). When f(n) = n^k, each level costs exactly r = a / b^k times the level above. So T(n) is a geometric series with ratio r, and the shape of that series decides the answer (Demo: merge sort, every level equal).

The three cases of the master theorem

Compare k with the critical exponent log_b a. It is the same test as r against 1.

Case	Test	Level sums	T(n)
1	k < logb a (r > 1)	grow toward the leaves	Θ(nlogb a): the leaves dominate
2	k = logb a (r = 1)	all the same	Θ(nk log n): one level's work times the height
3	k > logb a (r < 1)	shrink toward the leaves	Θ(f(n)): the root dominates

In a geometric series with r ≠ 1 the biggest term is a constant fraction of the whole, so only the biggest level counts. With r = 1 nothing shrinks, and all log n + 1 levels count. On the canvas, 3T(n/2) + n sums to 211, and its leaf level alone is 81 (Demo: 3T(n/2)+n, the leaves dominate). 2T(n/2) + n² sums to 496, less than twice its root's 256 (Demo: 2T(n/2)+n², the root dominates).

Worked examples

Algorithm	Recurrence	k vs logb a	T(n)
Binary search	T(n/2) + 1	0 = log₂ 1	Θ(log n), case 2
Merge sort	2T(n/2) + n	1 = log₂ 2	Θ(n log n), case 2
Karatsuba multiplication	3T(n/2) + n	1 < log₂ 3 ≈ 1.58	Θ(n1.58), case 1
Block matrix multiply, 8 products	8T(n/2) + n²	2 < log₂ 8 = 3	Θ(n³), case 1
Strassen, 7 products	7T(n/2) + n²	2 < log₂ 7 ≈ 2.81	Θ(n2.81), case 1
Quickselect with a good pivot	T(n/2) + n	1 > log₂ 1 = 0	Θ(n), case 3

Binary search is the thinnest tree: one call per level, each doing one comparison, so the sum is just the height (Demo: binary search, one call per level). Strassen's trick is all in case 1: one fewer product per call lowers a from 8 to 7, and with it the exponent of the leaf count.

When the theorem does not apply, the tree still works

The master theorem needs equal-size calls, a fixed a ≥ 1 and b > 1. T(n) = T(n−1) + n (insertion sort, a bad quicksort pivot) shrinks by subtraction, not division: its tree is a path of n levels costing n, n−1, …, 1, which sums to Θ(n²). T(n) = T(n/3) + T(2n/3) + n has unequal parts, but each full level still costs at most n and the longest path has log_3/2 n levels, so T(n) = Θ(n log n). The general form of the theorem for f(n) that is not a power of n also needs a regularity condition in case 3, and has a gap: 2T(n/2) + n/log n fits none of the three cases.

See also Quick Sort vs Merge Sort (the merge sort tree at work), Searching a Sorted List (binary search), Big-O Growth Race (how n log n, n^1.58 and n² compare), Plain Recursion vs Memoization vs Tabulation (a recursion tree with repeated subtrees) and Tail Calls and Tail-Call Optimization (the call stack of one path through the tree).

Karatsuba multiplication is case 1 with a = 3, b = 2: three half-size products give O(n^1.585).

The closest pair of points algorithm has the merge-sort recurrence T(n) = 2T(n/2) + O(n): linear strip work on each of log n levels.

What a Θ bound means, with c₁, c₂ and n₀ drawn as curves around f(n): see Big-O, Omega, Theta.

What the page leaves out

The canvas fixes n = 16, b = 2, T(1) = 1 and f(n) = n^k with constant 1, so every level sum is exact. It leaves out floors and ceilings when n is not a power of b, the extended case 2 for f(n) = n^k log^p n, the regularity condition, the substitution method for proving a guess, and the Akra–Bazzi method for unequal splits.

References

Master theorem (analysis of algorithms), Wikipedia

Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, chapter 4 (recurrences, recursion trees, the master method)

Jeff Erickson: Algorithms, chapter 1, recursion trees