A shortcut you have already earned
By now you have drawn enough recursion trees to feel the pattern: every divide-and-conquer cost obeys a recurrence of the shape T(n) = a T(n/b) + f(n), where a is how many subproblems you spawn, b is how much smaller each one is, and f(n) is the divide-plus-combine work you do at this level. In the previous guides you solved such recurrences two ways — by carefully summing a recursion tree level by level, or by the substitution method of guessing a bound and verifying it by induction. Both work, but both make you do real arithmetic every time. The master theorem is the payoff: a single lookup that hands you the answer for the whole family at once.
The whole theorem rests on one comparison. A recursion tree for T(n) = a T(n/b) + f(n) has about log base b of n levels, and at the very bottom the number of leaves is n^(log base b of a) — that exponent is so central it has a name, the critical exponent, written log_b a. Think of it as the benchmark cost: the work piled up at the leaves grows like n^(log_b a). The master theorem simply races your per-level work f(n) against that benchmark. Whichever grows faster controls the total — the leaves win, the root wins, or they tie. Those three outcomes are the theorem's three cases, and that is the entire idea.
The three cases, stated plainly
Here is the race in words. Case 1 (case one): the leaves win. If f(n) grows polynomially slower than n^(log_b a) — that is, f(n) = O(n^(log_b a - e)) for some constant e > 0 — then the cost piles up at the bottom of the tree, and T(n) = Theta(n^(log_b a)). The per-level work shrinks so fast as you climb up that the leaf level dwarfs everything above it.
Case 2 (case two): a tie. If f(n) grows at the same rate as the benchmark, f(n) = Theta(n^(log_b a)), then every level of the tree costs roughly the same, and there are about log base b of n levels. Same work per level, times that many levels, gives an extra logarithmic factor: T(n) = Theta(n^(log_b a) * log n). This is the case that explains why merge sort's T(n) = 2 T(n/2) + O(n) lands at Theta(n log n) — here log_b a = log_2 2 = 1, so the benchmark is n, f(n) = O(n) ties it, and the log n appears.
Case 3 (case three): the root wins. If f(n) grows polynomially faster than the benchmark, f(n) = Omega(n^(log_b a + e)) for some e > 0, then the top of the tree is the most expensive level and everything below shrinks geometrically beneath it, so T(n) = Theta(f(n)). The work you do combining at the very first call already dominates the whole recursion. Case 3 carries one extra string attached, which the next section is entirely about.
T(n) = a T(n/b) + f(n), benchmark = n^(log_b a)
Case 1: f(n) = O(n^(log_b a - e)) -> T(n) = Theta(n^(log_b a))
Case 2: f(n) = Theta(n^(log_b a)) -> T(n) = Theta(n^(log_b a) * log n)
Case 3: f(n) = Omega(n^(log_b a + e)) -> T(n) = Theta(f(n))
and a*f(n/b) <= c*f(n) for some c < 1 (regularity)The regularity condition, and the gaps in between
Case 3 needs a side promise to be true, called the regularity condition: a * f(n/b) <= c * f(n) for some constant c < 1 and all large enough n. In plain terms, it says the combine work really does shrink by a constant factor as you go one level deeper, so the geometric series of level-costs is dominated by its first term and genuinely sums to Theta(f(n)). For the well-behaved f(n) you meet in practice — powers of n, possibly times a log — this condition holds automatically, so it rarely bites. But it is not decoration: a pathological f(n) that grows fast yet oscillates can satisfy the Omega bound while failing regularity, and then case 3 simply does not apply.
Three quick traces
The method is mechanical once you trust it: compute the benchmark n^(log_b a), compare f(n) to it, name the case, read off the answer. Let us run three classic recurrences through it so the cases stop being abstract.
- Binary search, T(n) = T(n/2) + O(1): here a = 1, b = 2, so log_b a = log_2 1 = 0 and the benchmark is n^0 = 1. The work f(n) = O(1) ties the benchmark, so this is case 2, giving T(n) = Theta(1 * log n) = Theta(log n).
- Karatsuba multiplication, T(n) = 3 T(n/2) + O(n): here a = 3, b = 2, so log_b a = log_2 3 which is about 1.585, and the benchmark is n^1.585. The work f(n) = O(n) is polynomially smaller (n^1 versus n^1.585, a gap of n^0.585), so case 1 wins and T(n) = Theta(n^(log_2 3)), about Theta(n^1.585) — beating the schoolbook Theta(n^2).
- A combine-heavy split, T(n) = 2 T(n/2) + O(n^2): here a = 2, b = 2, so log_b a = 1 and the benchmark is n. The work f(n) = O(n^2) is polynomially larger (n^2 versus n, a gap of n), regularity holds (2*(n/2)^2 = n^2/2 <= c*n^2 with c = 1/2), so case 3 applies and T(n) = Theta(n^2) — the top level alone decides it.
What it covers, and what it does not
It is worth being honest about the master theorem's boundaries, because it is tempting to reach for it everywhere. It only solves recurrences of the exact form T(n) = a T(n/b) + f(n), with a constant number a >= 1 of subproblems, each of the same size n/b for a constant b > 1, and an f(n) that behaves polynomially. The moment the structure breaks that mold, the theorem has nothing to say. The same caveat from your earlier recurrence guides applies: this is a powerful special-case oracle, not a universal solver.
Two kinds of recurrence routinely fall outside it. First, uneven splits: a recurrence like T(n) = T(n/3) + T(2n/3) + O(n) has subproblems of different sizes, which a T(n/b) cannot express. Second, the gap recurrences the note above flagged, where f(n) sits within a log factor of the benchmark. For both, the next guide reaches for a strict generalization, the Akra-Bazzi method, which handles differing piece sizes and integrates over the combine work to give an answer where the master theorem shrugs. And underneath all of it, the recursion tree you learned first never stops working — every case of the master theorem is just a tree whose levels you have already learned to sum, packaged so you do not have to draw it again.