1
The recursion tree explains the three cases
Level i has aⁱ subproblems of size n/bⁱ. Whether the work grows, shrinks or stays level down the tree is exactly the comparison.
Lesson · Induction and Recursion · Recurrences
Divide-and-Conquer Recurrences
Algorithms that split a problem into a pieces of size n/b produce recurrences of one shape. The master theorem settles them by comparing log_b a with the exponent in f(n).
T(n) = a T(n/b) + nᵈ
case 1 log_b a < d ⟹ T(n) = Θ(nᵈ) root dominates
case 2 log_b a = d ⟹ T(n) = Θ(nᵈ log n) every level equal
case 3 log_b a > d ⟹ T(n) = Θ(n^{log_b a}) leaves dominate
One comparison, three cases
Core ideas
What this lesson establishes
The three cases are not arbitrary: they are which level of the recursion tree carries most of the work.
2
Merge sort is the balanced case
a = 2, b = 2, d = 1, so log₂2 = 1 = d. Every level does Θ(n) work and there are log n levels.
3
Fewer, bigger pieces can beat more, smaller ones
Karatsuba multiplication does 3 multiplications of half-size instead of 4, and log₂3 ≈ 1.585 < 2 is the entire improvement.
The material
The master theorem
Where the recurrence comes from, what the tree looks like, and the statement.
A divide-and-conquer algorithm splits an input of size n into a subproblems of size n/b, solves each recursively, and spends f(n) combining. The running time therefore satisfies T(n) = aT(n/b) + f(n).
The recursion tree
level subproblems size work per level
0 1 n f(n)
1 a n/b a·f(n/b)
2 a² n/b² a²·f(n/b²)
…
L a^L 1 a^L · f(1)
with L = log_b n levels, so a^L = a^{log_b n} = n^{log_b a}.
With f(n) = nᵈ, the work at level i is aⁱ(n/bⁱ)ᵈ = nᵈ(a/bᵈ)ⁱ — a geometric series in i with ratio a/bᵈ. Which end dominates depends entirely on whether that ratio is less than, equal to, or greater than 1, and a/bᵈ compared with 1 is log_b a compared with d. That is the whole theorem.
Definition · The Θ notation, as much as is needed here
T(n) = Θ(g(n)) means T(n) is trapped between two positive constant multiples of g(n) for all large enough n: c₁ g(n) ≤ T(n) ≤ c₂ g(n) once n is past some threshold. It names a growth rate and discards the constants. “Big-O, Big-Omega and Big-Theta” in Algorithms and Complexity makes this precise and works with it; here it is only the shape of the answer the theorem reports.
Theorem · Master theorem (polynomial form)
Let T(n) = aT(n/b) + Θ(nᵈ) with a ≥ 1, b > 1, d ≥ 0. Then T(n) = Θ(nᵈ) if log_b a < d; T(n) = Θ(nᵈ log n) if log_b a = d; and T(n) = Θ(n^{log_b a}) if log_b a > d.
The cases are numbered here in the order of the comparison — less, equal, greater — so case 1 is the root dominating and case 3 the leaves, and the lab below and Algorithms and Complexity use the same numbering. Some texts number them the other way round. When there is any doubt, name a case by what dominates rather than by its number.
Example · Merge sort
T(n) = 2T(n/2) + n: a = 2, b = 2, d = 1, log₂2 = 1 = d. Balanced case, so Θ(n log n). Every level does n units of merging and there are log₂ n levels.
Example · Binary search
T(n) = T(n/2) + 1: a = 1, b = 2, d = 0, log₂1 = 0 = d. Balanced again, so Θ(log n). One subproblem and constant work per level.
Example · Karatsuba multiplication
Multiplying two n-digit numbers by splitting into halves needs four half-size products naively: T(n) = 4T(n/2) + n, and log₂4 = 2 > 1, giving Θ(n²) — no better than the schoolbook method. Karatsuba's identity does it with three: T(n) = 3T(n/2) + n, and log₂3 ≈ 1.585, giving Θ(n^{1.585}). One fewer multiplication changes the exponent.
Two cautions. The theorem as stated covers f(n) = Θ(nᵈ); forcing terms like n log n fall between the cases and need the fuller version. And it says nothing about constants — an algorithm with a better exponent may lose on realistic inputs, which is why Karatsuba is used for large numbers and schoolbook multiplication for small ones.
Theorem · Substituting to make it linear
Setting n = bᵏ and Sₖ = T(bᵏ) turns T(n) = aT(n/b) + nᵈ into Sₖ = aSₖ₋₁ + (bᵈ)ᵏ, an ordinary linear recurrence that “Solving Linear Recurrences” solves. The master theorem is that solution, read back.
Interactive
Algorithms and growth
Counts from running, not from quoting
Method
Applying the master theorem
Read off a, b, d, then compare.
1
Identify a, b and d
a is the number of subproblems, b the shrink factor, d the exponent of the combining work. Reading a off as the shrink factor is the standard slip.
2
Compute log_b a
log₂ 2 = 1, log₂ 3 ≈ 1.585, log₂ 4 = 2, log₂ 8 = 3. These four cover most examples.
3
Compare with d and read the case
Less, equal, greater — root dominates, level, leaves dominate.
4
Sanity check with the tree
Does the work per level grow, stay constant or shrink? The answer should match the case you selected.
Master theorem
Score 0 / 0Choose the answer you can justify.
Three recurrences
Same theorem, three different answers.
1. T(n) = 2T(n/2) + n a=2 b=2 d=1
log₂2 = 1 = d → CASE 2 → Θ(n log n) merge sort
2. T(n) = 8T(n/2) + n² a=8 b=2 d=2
log₂8 = 3 > 2 → CASE 3 → Θ(n³) naive matrix mult.
3. T(n) = 2T(n/2) + n² a=2 b=2 d=2
log₂2 = 1 < 2 → CASE 1 → Θ(n²) root dominates
Strassen improves case 2 above by using 7 multiplications, not 8:
T(n) = 7T(n/2) + n², log₂7 ≈ 2.807 → Θ(n^2.807)
Case 3 is the one where the recursion is doing the damage: n³ work arises from n^{log₂8} leaves, not from the combining. Strassen attacks exactly that by reducing a from 8 to 7, and gains an exponent improvement that no faster combining step could have produced.
Common mistakes
1
Mixing up a and ba counts subproblems, b is the shrink factor. T(n) = 2T(n/3) + n has a = 2, b = 3, and swapping them gives the wrong case.
2
Applying the polynomial form to a non-polynomial ff(n) = n log n falls between the balanced case and the case where the root dominates — it outgrows n^{log_b a} but not by a power of n — and needs the general statement. Forcing it into the version here gives a wrong answer.
3
Reading Θ as a statement about real running timeIt describes asymptotic growth. An algorithm with a better exponent and a worse constant can be slower on every input you will ever run.
Check your understanding
✓
Finish when you can decide the case from the tree, not from the formula.
For T(n) = 3T(n/4) + n, compute the work at levels 0, 1 and 2 and say whether it is growing or shrinking. Then check that the master theorem gives the case your tree predicted.
Note: The master theorem does not cover every divide-and-conquer recurrence: unequal splits like T(n) = T(n/3) + T(2n/3) + n need the tree argument directly, and that one turns out to be Θ(n log n) — the same as an even split, which is why quicksort survives an imperfect pivot.