The Master Theorem

Drawing a recursion tree for every divide-and-conquer recurrence gets old fast — especially when the answer always comes down to the same question: does the work pile up at the root, at the leaves, or spread evenly across the levels? The master theorem is that recursion-tree argument, done once, in general, and packaged as a lookup table. For any recurrence of the form T(n) = a\,T(n/b) + f(n) you read off the answer by comparing two functions — no tree, no induction, just a comparison.

It is the single most-used tool in algorithm analysis: merge sort, binary search, Karatsuba, Strassen, the median-of-medians select — most fall to it in one line. This page is about wielding it fluently and knowing its blind spot, because it does not cover every recurrence, and misapplying it is a classic exam trap.

The watershed function

Everything hinges on one quantity built from a and b alone — the watershed, or critical exponent:

n^{\log_b a}.

Where does it come from? The recursion tree has depth \log_b n and branches by a each level, so the bottom level has a^{\log_b n} = n^{\log_b a} leaves. That is the total cost of all the leaves — the work done "at the bottom." The theorem compares your f(n) (the cost "at the top and middle") against this leaf cost n^{\log_b a}, and whichever grows faster wins.

So the whole method is a race between two competing terms — f(n) versus n^{\log_b a}. The chart shows the race for Strassen's matrix multiply, T(n) = 7\,T(n/2) + n^2: here \log_2 7 \approx 2.807, so the watershed n^{2.807} outruns f(n) = n^2. The leaves dominate, and T(n) = \Theta(n^{2.807}).

The three cases

Compare f(n) with the watershed n^{\log_b a}. There are three ways the race can end — and note the word polynomially: in cases 1 and 3 the gap between the two must be at least a factor of n^{\varepsilon} for some fixed \varepsilon > 0, not merely a logarithm.

Case	Condition on f(n)	Who wins	Solution T(n)
1	f(n) = O\!\big(n^{\log_b a - \varepsilon}\big) — polynomially smaller	leaves	\Theta\!\big(n^{\log_b a}\big)
2	f(n) = \Theta\!\big(n^{\log_b a}\log^k n\big),\; k \ge 0 — the same order	every level equally	\Theta\!\big(n^{\log_b a}\log^{k+1} n\big)
3	f(n) = \Omega\!\big(n^{\log_b a + \varepsilon}\big) — polynomially larger (+ regularity)	root	\Theta\!\big(f(n)\big)

Case 2 is the everyday one (take k = 0): when f(n) = \Theta(n^{\log_b a}), the two terms tie, work spreads evenly over \log n levels, and you gain exactly one logarithmic factor. Cases 1 and 3 are the lopsided races where one side runs away.

Case 3 needs more than "f is bigger." You must also check the regularity condition: a\,f(n/b) \le c\,f(n) for some constant c < 1 and all large n.
It says the work genuinely shrinks as you recurse, so the root really dominates. Every polynomial f(n) = n^d with d > \log_b a satisfies it automatically; pathological, wildly oscillating f can fail it, and then case 3 does not apply even though f looks bigger.

One example per case

The recipe is always: compute \log_b a, compare f(n) to n^{\log_b a}, pick the case.

Merge sort — case 2. T(n) = 2\,T(n/2) + n. Here \log_2 2 = 1, watershed n^1 = n, and f(n) = n = \Theta(n^1) — a tie. Case 2 with k = 0 gives \Theta(n\log n).
Binary search — case 2. T(n) = T(n/2) + \Theta(1). \log_2 1 = 0, watershed n^0 = 1, and f(n) = \Theta(1) = \Theta(n^0) — again a tie. Case 2 gives \Theta(n^0 \log n) = \Theta(\log n).
Strassen — case 1. T(n) = 7\,T(n/2) + \Theta(n^2). \log_2 7 \approx 2.807, and f(n) = n^2 = O(n^{2.807 - \varepsilon}) is polynomially smaller. The leaves win: \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807}).
A root-heavy split — case 3. T(n) = 2\,T(n/2) + n^2. \log_2 2 = 1, and f(n) = n^2 = \Omega(n^{1+\varepsilon}) is polynomially larger. Regularity: 2\,(n/2)^2 = n^2/2 \le \tfrac12\,n^2, so c = \tfrac12 < 1 holds. The root wins: \Theta(n^2).

In case 2 every level of the recursion tree costs about the same — for merge sort, exactly n per level. There is nothing to make one level dominate, so the total is the per-level cost times the number of levels, and the number of levels is \log_b n. That is literally where the \log n in \Theta(n\log n) comes from — it is a level count, not a mysterious extra. The general case 2 with a \log^k n in f pushes this one step further: summing \log^k over \log n levels integrates up to \log^{k+1} n, which is why the exponent on the log goes up by one.

Cases 1 and 3 demand a polynomial gap — a whole factor of n^{\varepsilon} — between f(n) and the watershed. When the gap is only logarithmic, you fall into the theorem's blind spot and none of the three cases applies. The textbook example is T(n) = 2\,T(n/2) + n/\log n: here f(n) = n/\log n is smaller than the watershed n, but only by a \log n factor — not by any n^{\varepsilon} — so case 1 is off the table, and it is not \Theta(n) either. (The true answer, \Theta(n\log\log n), needs the Akra–Bazzi method.) A second trap: case 3's regularity condition can fail even when f looks bigger. When the master theorem is silent, don't force it — fall back to a recursion tree or Akra–Bazzi.