The master theorem, and the recurrences it refuses to solve

Divide-and-conquer recurrences all have the same shape, so there is a formula. The marks are lost in two places: comparing the wrong pair of functions, and not noticing when the theorem does not apply at all.

The form

T(n) = a·T(n/b) + f(n)          a ≥ 1,  b > 1

a subproblems, each of size n/b, plus f(n) to split and combine. Everything turns on comparing f(n) against the watershed function:

n^(log_b a)

That exponent is the number of leaves in the recursion tree, and the comparison asks whether the work is dominated by the leaves, the root, or spread evenly.

The three cases

Case 1 — leaves win. If f(n) = O(n^(log_b a - ε)) for some ε > 0:

T(n) = Θ(n^(log_b a))

Case 2 — balanced. If f(n) = Θ(n^(log_b a) · logᵏ n) for some k ≥ 0:

T(n) = Θ(n^(log_b a) · log^(k+1) n)

Case 3 — root wins. If f(n) = Ω(n^(log_b a + ε)) for some ε > 0, and the regularity condition a·f(n/b) ≤ c·f(n) holds for some c < 1 and large n:

T(n) = Θ(f(n))

The ε matters. The gap has to be polynomial — a factor of log n is not enough, and that is precisely where the trap questions live.

Worked

Merge sort. T(n) = 2T(n/2) + n

log_b a = log₂ 2 = 1  →  watershed n¹ = n
f(n) = n = Θ(n¹ log⁰ n)          case 2 with k = 0
T(n) = Θ(n log n)

Binary search. T(n) = T(n/2) + 1

log_b a = log₂ 1 = 0  →  watershed n⁰ = 1
f(n) = 1 = Θ(1 · log⁰ n)         case 2 with k = 0
T(n) = Θ(log n)

Strassen. T(n) = 7T(n/2) + n²

log_b a = log₂ 7 ≈ 2.807  →  watershed n^2.807
f(n) = n² = O(n^(2.807 - 0.8))   case 1
T(n) = Θ(n^2.807)

Beating the naive Θ(n³) — the recursion tree is leaf-heavy, so the combine step is irrelevant.

Root-heavy. T(n) = 2T(n/2) + n²

watershed n¹;  f(n) = n² = Ω(n^(1+1))       case 3 candidate
regularity: 2(n/2)² = n²/2 ≤ c·n² with c = 1/2 < 1   ✓
T(n) = Θ(n²)

Case 2 with k = 1. T(n) = 2T(n/2) + n log n

watershed n¹;  f(n) = n log n = Θ(n¹ log¹ n)    k = 1
T(n) = Θ(n log² n)

Answering Θ(n log n) here is the single most common slip. k increments.

Where it fails

T(n) = 2T(n/2) + n / log n

Watershed is n. Is f(n) = n/log n polynomially smaller? The ratio is log n, which is smaller than n^ε for every ε > 0. So the gap is not polynomial, case 1 does not apply, and it is not Θ(n log⁰ n) either. The master theorem is silent.

Solve it with the recursion tree instead. Level i has 2ⁱ nodes of size n/2ⁱ, each costing (n/2ⁱ)/log(n/2ⁱ):

level i cost = 2ⁱ · (n/2ⁱ)/(log n - i) = n/(log n - i)

total = Σ_{i=0}^{log n - 1} n/(log n - i) = n · H_{log n} = Θ(n log log n)

using the harmonic sum H_m = Θ(log m).

Two more shapes the theorem does not cover, both of which show up in exams:

• Unequal splits, T(n) = T(n/3) + T(2n/3) + n → recursion tree, or Akra–Bazzi. Answer Θ(n log n).
• Non-constant b, T(n) = T(√n) + 1 → substitute n = 2ᵐ, giving S(m) = S(m/2) + 1 = Θ(log m) = Θ(log log n).

The checklist I run in an exam

1. Read off a, b, f(n). Compute log_b a.
2. Write the watershed n^(log_b a) beside f(n).
3. Is the gap polynomial? If not, stop — recursion tree.
4. Case 3 also needs the regularity check.
5. Case 2: count the existing powers of log, then add one.

What to take forward

• The comparison is always f(n) against n^(log_b a), never against n.
• A log n gap is not a polynomial gap — that is the gap case.
• Case 2 with logᵏ n gives log^(k+1) n.
• When the theorem does not apply, the recursion tree always does.

---

— Ishaan SandhwarAlgorithmsGATEComplexity