The Master Theorem

The one comparison the whole theorem turns on

Every divide-and-conquer algorithm tells the same story: split the input into a pieces, each of size n/b, solve them recursively, then spend f(n) time stitching the answers back together. Merge sort splits into 2 halves and merges in linear time. Strassen's matrix multiply splits into 7 subproblems of half-size. Binary search recurses on 1 half and does constant comparison work. Each of these is the same recurrence with different knobs:

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

The Master Theorem says you can solve any recurrence of this shape by answering one question: does the recursion spend most of its time at the leaves, at the root, or evenly across every level? The whole method is a single comparison between f(n) and a quantity called the watershed function, n^(log_b a).

Where does n^(log_b a) come from? Picture the recursion tree. The root does f(n) work and has a children, each of size n/b. Their children are size n/b², and so on. The tree has depth log_b(n), and at the bottom there are a^(log_b n) leaves. By the change-of-base identity, a^(log_b n) = n^(log_b a). So n^(log_b a) is literally the number of base cases — the unavoidable floor of work the recursion must do just to reach the bottom.

The three cases, precisely

Let c = log_b a (the critical exponent). Compare f(n) against n^c:

Case 1 — leaves dominate. If f(n) = O(n^(c − ε)) for some constant ε > 0 (the combine work is polynomially smaller than the leaf work), the leaves win:

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

Case 2 — every level costs the same. If f(n) = Θ(n^c), work is spread evenly across all log_b n levels, so you multiply by the number of levels:

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

Case 3 — the root dominates. If f(n) = Ω(n^(c + ε)) for some ε > 0 and the regularity condition a·f(n/b) ≤ k·f(n) holds for some constant k < 1 and large n, the top level swamps everything below it:

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

The mental shortcut: compute c = log_b a, then ask whether f(n) grows slower than, the same as, or faster than n^c. The word polynomially is load-bearing in Cases 1 and 3 — f(n) must differ by a factor of at least n^ε, not just a logarithm. That gap is exactly where the theorem stops working.

Four algorithms read off in seconds

Watch how fast the method runs once you internalize c = log_b a:

• Merge sort: T(n) = 2T(n/2) + Θ(n). Here c = log₂ 2 = 1 and f(n) = Θ(n) = Θ(n¹). They match → Case 2 → Θ(n log n).
• Binary search: T(n) = T(n/2) + Θ(1). Now c = log₂ 1 = 0, so n^c = n⁰ = 1 and f(n) = Θ(1). Match → Case 2 → Θ(log n).
• Strassen's matrix multiply: T(n) = 7T(n/2) + Θ(n²). Here c = log₂ 7 ≈ 2.807, which exceeds 2, so the leaf cost n^2.807 beats f(n) = n² polynomially → Case 1 → Θ(n^2.807), famously below the naïve Θ(n³).
• A combine-heavy split: T(n) = 2T(n/2) + Θ(n²). Now c = 1 but f(n) = n² dwarfs n¹, and 2·(n/2)² = n²/2 ≤ ½·n² satisfies regularity → Case 3 → Θ(n²).

Karatsuba multiplication is another clean Case 1: T(n) = 3T(n/2) + Θ(n) gives c = log₂ 3 ≈ 1.585, so multiplying two n-digit numbers costs Θ(n^1.585) instead of the schoolbook Θ(n²).

When the Master Theorem applies — and when it doesn't

• Use it whenever the subproblem size is n/b for a constant b > 1 and every subproblem is the same size. This covers the vast majority of textbook divide-and-conquer algorithms.
• Don't use it for decrease-and-conquer recurrences like T(n) = T(n−1) + f(n) — the size shrinks additively, not by a ratio. Those are solved by summation.
• Don't use it when subproblems have unequal sizes, like T(n) = T(n/3) + T(2n/3) + n. The single ratio b doesn't exist; reach for Akra-Bazzi.
• Watch the gap: when f(n) beats n^c by only a logarithmic factor (e.g. f(n) = n^c log n), no case applies. The extended Case 2 or Akra-Bazzi rescues you.

One reassurance: floors and ceilings don't matter. Whether your code recurses on ⌊n/2⌋ or ⌈n/2⌉, the asymptotic answer is identical — the rounding perturbs subproblem sizes by at most 1 and disappears in Θ notation. CLRS proves this so you can drop the brackets when applying the theorem.

Master Theorem vs the other recurrence solvers

	Master Theorem	Recursion tree	Substitution	Akra-Bazzi	Generating functions
Recurrence shape	aT(n/b) + f(n), equal pieces	any	any (need a guess)	Σ aᵢT(n/bᵢ) + g(n), unequal pieces	linear, constant-coefficient
Effort	seconds — one comparison	draw + sum levels	guess then prove by induction	evaluate one integral	algebra on power series
Gives	tight Θ bound	tight Θ (if summed right)	upper/lower bound you guessed	tight Θ bound	exact closed form
Handles unequal subproblems	no	yes (tedious)	yes	yes — its whole point	no
Handles f(n)=n log n gap	no (needs extended form)	yes	yes	yes	n/a
Risk of error	misjudging "polynomially" gap	arithmetic on the level sums	guessing wrong, then forcing it	setting up the integral	partial-fraction slips
Best for	standard D&C algorithms	building intuition / odd shapes	verifying a known answer	uneven splits, weird f(n)	exact counts, not asymptotics

The Master Theorem is the fastest tool but the least general. The recursion tree is its honest cousin — slower, but it works on anything and shows you why the answer is what it is, which is exactly why the visualization on this page draws the tree. Akra-Bazzi is the heavy artillery for when the splits go uneven.

What the cases cost in real terms

• Case 2 dominates real algorithms. Merge sort sorting 1,000,000 elements does ≈ n log₂ n ≈ 2 × 10⁷ comparison-level operations — about 20 levels of the tree, each costing one full pass of n. That's the log n factor made concrete.
• Strassen's Case-1 win is real but late. n^2.807 beats n³ only once the constant-factor overhead of 7 multiplies plus 18 adds is amortized — typically past n ≈ 1000–2000 in practice, which is why BLAS libraries cross over to Strassen only for very large matrices.
• The critical exponent is exquisitely sensitive to a. Going from 7 to 8 subproblems in aT(n/2) jumps the exponent from log₂ 7 ≈ 2.807 to log₂ 8 = 3 — Strassen's entire advantage is the difference between 7 and 8 multiplications.
• The log factor never costs more than the polynomial. For 1,000,000 elements, log₂ n ≈ 20 — a 20× factor, dwarfed by the n itself. That's why Case 2's n log n is "almost linear" for practical purposes.

JavaScript: classify a recurrence automatically

// Solve T(n) = a·T(n/b) + f(n) where f(n) = Θ(n^d · (log n)^k).
// Returns the asymptotic class as a human-readable string.
function masterTheorem(a, b, d, k = 0) {
  if (a < 1 || b <= 1) throw new Error("need a ≥ 1 and b > 1");

  const c = Math.log(a) / Math.log(b);        // critical exponent log_b(a)
  const EPS = 1e-9;

  if (d < c - EPS) {
    // Case 1 — leaves dominate (f grows polynomially slower than n^c)
    return `Θ(n^${round(c)})`;
  }
  if (Math.abs(d - c) <= EPS) {
    // Case 2 (extended) — tie; pick up the log factors
    if (k >= 0) return `Θ(n^${round(c)} · (log n)^${k + 1})`;
    if (k === -1) return `Θ(n^${round(c)} · log log n)`;
    return `Θ(n^${round(c)})`;               // k < -1
  }
  // Case 3 — root dominates (assumes the regularity condition holds)
  return `Θ(n^${round(d)}${k ? ` · (log n)^${k}` : ""})`;
}

const round = x => Number.isInteger(x) ? x : x.toFixed(3);

console.log(masterTheorem(2, 2, 1));   // merge sort   → Θ(n^1 · (log n)^1)
console.log(masterTheorem(1, 2, 0));   // binary search→ Θ(n^0 · (log n)^1)
console.log(masterTheorem(7, 2, 2));   // Strassen     → Θ(n^2.807)
console.log(masterTheorem(2, 2, 2));   // combine-heavy→ Θ(n^2)
console.log(masterTheorem(3, 2, 1));   // Karatsuba    → Θ(n^1.585)

Two things worth flagging. First, this encodes the extended Master Theorem: the k parameter lets Case 2 absorb a (log n)^k factor in f(n), so it can handle the gap recurrences the plain three-case form can't. Second, Case 3 silently assumes the regularity condition — for every polynomial f(n) that's safe, but the code can't verify it for an arbitrary symbolic f, so don't trust it on exotic functions.

Python: a recursion-tree checker

import math

def master_theorem(a, b, d, k=0):
    """Solve T(n) = a*T(n/b) + Theta(n**d * (log n)**k)."""
    if a < 1 or b <= 1:
        raise ValueError("need a >= 1 and b > 1")

    c = math.log(a, b)            # critical exponent log_b(a)
    fmt = lambda x: int(x) if float(x).is_integer() else round(x, 3)

    if d < c - 1e-9:              # Case 1: leaves win
        return f"Theta(n^{fmt(c)})"
    if abs(d - c) <= 1e-9:        # Case 2 (extended): tie
        if k >= 0:
            return f"Theta(n^{fmt(c)} * (log n)^{k + 1})"
        if k == -1:
            return f"Theta(n^{fmt(c)} * log log n)"
        return f"Theta(n^{fmt(c)})"
    # Case 3: root wins (regularity condition assumed)
    tail = f" * (log n)^{k}" if k else ""
    return f"Theta(n^{fmt(d)}{tail})"


def tree_levels(a, b, n):
    """Sum work per recursion-tree level to SHOW which case is firing.
    Cost at depth i = a**i * f(n / b**i), with f(m) = m here (linear combine)."""
    levels, depth = [], 0
    m = n
    while m >= 1:
        levels.append(a ** depth * (m))   # a^i subproblems, each costing ~m
        m //= b
        depth += 1
    return levels


print(master_theorem(2, 2, 1))   # merge sort   -> Theta(n^1 * (log n)^1)
print(master_theorem(7, 2, 2))   # Strassen     -> Theta(n^2.807)
print(master_theorem(2, 2, 0))   # binary-ish   -> Theta(n^1)  (leaves win)

# Watch the per-level work for merge sort: every level sums to ~n.
print(tree_levels(2, 2, 16))     # [16, 16, 16, 16, 16] -> flat -> Case 2

The tree_levels helper is the whole intuition in five lines: for merge sort it prints a flat list — every level costs the same n — which is the visual signature of Case 2. For a Case-1 recurrence the level costs grow toward the leaves; for Case 3 they shrink toward them.

Variants worth knowing

The extended (general) Master Theorem. Replaces Case 2 with: if f(n) = Θ(n^c · (log n)^k) with k ≥ 0, then T(n) = Θ(n^c · (log n)^(k+1)). This closes the most common gap — recurrences like T(n) = 2T(n/2) + n log n become Θ(n log² n) instead of falling through the cracks.

The Akra-Bazzi method. The true generalization. For T(n) = Σ aᵢ T(n/bᵢ) + g(n) with possibly different subproblem sizes, find the unique p solving Σ aᵢ / bᵢ^p = 1, then T(n) = Θ(n^p · (1 + ∫₁ⁿ g(u)/u^(p+1) du)). The Master Theorem is the special case where all bᵢ are equal, and p reduces to log_b a.

The decrease-by-a-constant cousin. For T(n) = a·T(n−c) + f(n) (e.g. naïve recursive Fibonacci, a=2, c=1), there's a separate "master theorem for subtract-and-conquer" that yields exponential or polynomial bounds depending on whether a > 1. Don't confuse it with the divide version.

The continuous Master Theorem. Used in analyzing parallel and cache-oblivious algorithms, where subproblem sizes are real numbers rather than integers and the recursion is modeled as an integral equation.

Common mistakes and edge cases

• Forgetting "polynomially." In Cases 1 and 3, f(n) must differ from n^c by a factor of n^ε, not just a log. T(n) = 2T(n/2) + n log n is not Case 1, 2, or 3 — it lands in the gap.
• Skipping the regularity check in Case 3. It almost always holds for polynomials, but pathological f(n) (oscillating or super-polynomial-with-dips) can fail it, and then Case 3 simply doesn't apply.
• Applying it to unequal splits. T(n) = T(n/3) + T(2n/3) + n has no single b. The answer is Θ(n log n), but only Akra-Bazzi or a recursion tree gets you there.
• Confusing a with b. a is how many subproblems you spawn; b is how much smaller each one is. 3T(n/2) is three half-size problems, not two third-size ones.
• Treating it as decrease-and-conquer. T(n) = T(n−1) + 1 is Θ(n), not Θ(log n) — the size shrinks by subtraction, so the Master Theorem doesn't apply at all.
• Ignoring non-polynomial f(n). If f(n) = n / log n, it's smaller than n but not polynomially smaller, so it sneaks into the gap even though it looks like Case 1.