The Master Theorem and the Recursion Tree Behind Its Three Cases

A recurrence such as T(n) = 2T(n/2) + n states a cost in terms of a smaller cost of the same shape. Turning that statement into a class requires comparing two quantities: the work performed by the top-level call and the total work performed by the subproblems at the bottom of the recursion. The master theorem is a table of the three possible outcomes of that comparison, and its three cases are the three ways a recursion tree can distribute its work.

The recurrence form and the watershed exponent

The theorem applies to

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

where a counts the subproblems, n/b their size, and f(n) the work the current call does outside its recursive calls. The comparison is entirely between f(n) and the power of n fixed by the recursion structure:

p = log_b a

That exponent is the number of leaves in the tree, expressed as a function of n: there are a^k nodes at depth k, each with subproblem size n / b^k, and the recursion bottoms out at depth log_b n. Substituting gives a^(log_b n) = n^(log_b a) = n^p. The three cases then read as follows, with ε > 0:

Case	Condition on f(n)	Result
1	f(n) = O(n^(p−ε))	T(n) = Θ(n^p), leaf-dominated
2	f(n) = Θ(n^p log^k n), k ≥ 0	T(n) = Θ(n^p log^(k+1) n), balanced
3	f(n) = Ω(n^(p+ε)) and the regularity condition holds	T(n) = Θ(f(n)), root-dominated

The strict inequality in cases 1 and 3 matters. A gap of zero between f(n) and n^p is case 2, and the extra logarithm that case 2 appends is exactly the depth of the tree: when every level costs the same, the total is the level cost times the number of levels.

Worked examples

Merge sort yields T(n) = 2T(n/2) + Θ(n). Here a = b = 2 and p = log₂ 2 = 1, so f(n) = Θ(n^1) and case 2 applies with k = 0, giving Θ(n log n). At n = 1024 the tree has log₂ 1024 = 10 levels below the root and the per-level work is proportional to 1024, so the comparison-scale total is about 1024 × 11.

Binary search yields T(n) = T(n/2) + 1. Now p = log₂ 1 = 0 and f(n) = Θ(1) = Θ(n^0), which is case 2 again, giving Θ(log n). For n = 1024 that is 10 probes, and the depth of the tree is the answer.

Strassen’s matrix multiplication yields T(n) = 7T(n/2) + Θ(n²). The watershed exponent is p = log₂ 7 ≈ 2.807, and f(n) = Θ(n²) is polynomially smaller, so case 1 gives Θ(n^2.807). At n = 1024 the exponent translates to about 2.8 × 10⁸ units of work against roughly 1.07 × 10⁹ for the cubic algorithm, a factor near 3.8 in favour of the recursive form. Karatsuba’s integer multiplication has the same shape, T(n) = 3T(n/2) + Θ(n), with p = log₂ 3 ≈ 1.585; at 4096 bits the recursive bound corresponds to about 5.3 × 10⁵ basic operations against 1.7 × 10⁷ for schoolbook multiplication.

Both figures count operations on bits, which is the unit that the word-RAM cost model makes explicit.

A case 3 example completes the set. The recurrence T(n) = 2T(n/2) + n² has p = 1 and f(n) = n², which is polynomially larger, and the regularity condition holds with room to spare: 2·f(n/2) = n²/2 ≤ (1/2)·f(n), so any c between one half and one works. Level k of the tree costs 2^k·(n/2^k)² = n²/2^k, a decreasing geometric series with ratio one half, so the root’s n² already dominates the sum of everything below it, and the answer is Θ(n²) rather than Θ(n² log n). The tree makes the cancellation visible in a way the table does not: each level of the merge-sort shape pays the same, and each level of this shape pays half the previous one, so only the first few levels matter at all.

One more row of the same table shows case 2 with k = 0 at a different p: T(n) = 4T(n/2) + n² has p = log₂ 4 = 2, so f(n) sits exactly on the watershed and the result is Θ(n² log n), not Θ(n²). Doubling the branching factor without changing the per-call work adds a full logarithmic factor, because the number of levels is unchanged while the per-level cost stays flat instead of shrinking.

Why the third case needs a regularity condition

Case 3 claims that the root does more work than all its descendants combined, which can only be true if f decreases geometrically along the tree. The condition states that for some constant c < 1,

a·f(n/b) ≤ c·f(n)

for all sufficiently large n. When it holds, the total cost of all descendants of the root is bounded by a geometric series f(n)(1 + c + c² + …) = f(n)/(1 − c), and the conclusion Θ(f(n)) follows. The condition is sufficient rather than necessary, so a recurrence that violates it may still satisfy the conclusion.

Oscillating functions violate it. Take f(n) = n(2 + sin n), which stays inside Θ(n) and is therefore never polynomially smaller than a root term of order n. The quantity the condition bounds is a·f(n/2)/f(n), which here equals (2 + sin(n/2)) / (2 + sin n); the two arguments take opposite extreme values infinitely often, and where sin(n/2) ≈ 1 and sin n ≈ −1 the quantity is near 3, so no c < 1 can bound it. The bound on the tail of the tree fails even though the shape of the recurrence suggests the root should dominate.

Polylogarithmic factors are the other common trap. Consider T(n) = 2T(n/2) + n log n. With p = 1, case 1 demands f(n) = O(n^(1−ε)) and case 3 demands f(n) = Ω(n^(1+ε)), so neither applies; the function sits exactly on the watershed with a logarithmic surplus. The polylogarithmic version of case 2 covers it, giving T(n) = Θ(n log² n). Several abbreviated statements of the theorem omit that version, and a bound like Θ(n log n) for this recurrence is wrong by a factor of log n, which at n = 10⁶ is about 20.

Recurrences with uneven splits

A recurrence with different divisors for different subproblems has no single b, and the master theorem does not apply in that form. Selection with the median-of-medians pivot gives

T(n) = T(n/5) + T(7n/10) + Θ(n)

because the recursive call that finds the pivot operates on one fifth of the input and the surviving call on at most seven tenths. Akra and Bazzi generalize the watershed idea: for T(n) = Σ aᵢ·T(n/bᵢ) + g(n), the exponent p solves Σ aᵢ·bᵢ^(−p) = 1, and then T(n) = Θ(n^p·(1 + ∫₁ⁿ g(u)/u^(p+1) du)). Here the equation (1/5)^p + (7/10)^p = 1 has its root near p ≈ 0.84, and the integral evaluates to Θ(n^(1−p)), so the product gives Θ(n). Selection is linear precisely because the two fractions sum to less than one. Change the split to 1/5 and 9/10 and the same equation has its root near p ≈ 1.28, so the recurrence becomes superlinear, of order n^1.28.

Two other shapes are worth recognising because they evade the theorem entirely. A recurrence that shrinks by a constant amount, T(n) = T(n−1) + n, sums an arithmetic series and gives Θ(n²). A recurrence whose split fraction approaches one half from below, T(n) = T(αn) + T((1−α)n) + n for constant α, has logarithmic depth and gives Θ(n log n) despite having no fixed divisor.

A subtler boundary condition is rounding. The theorem is stated for n/b, but real recurrences divide sizes that do not divide evenly: merge sort on 1025 elements makes one call on 512 and one on 513. The formal statements that cover this replace n/b with ⌈n/b⌉ or ⌊n/b⌋, and the asymptotic conclusions are unchanged because the rounding perturbs each level’s cost by at most a constant factor while the geometric structure of the level totals is preserved. The rounding does interact with the base case: with ⌈n/b⌉ the recursion on size 1 can call itself on size 1 again unless the recurrence stops at an explicit threshold, which is why implementations cut off at a small constant size rather than at 1.

import math

def level_costs(n, a, b, f):
    """Cost per level of the tree for T(n) = a*T(n/b) + f(n), root first."""
    depth = int(round(math.log(n, b)))
    return [(a ** k, n // b ** k, (a ** k) * f(n // b ** k)) for k in range(depth + 1)]

rows = level_costs(1024, 2, 2, lambda size: size)      # merge sort shape
for nodes, size, cost in rows:
    print(f'level nodes={nodes:>4} size={size:>4} cost={cost:>6}')

Every row of the merge-sort output has the same cost, which is what case 2 asserts: the depth of the tree is the only thing multiplied by the level cost.

Reading a bound off the tree instead of the table

The table is a shortcut for an argument that can always be done directly. The steps are to write down the number of nodes at each level, multiply by the cost of a subproblem at that level, and compare the resulting geometric series with the leaf count n^p.

For T(n) = 2T(n/2) + n log n, level k holds 2^k nodes of size n/2^k, each costing (n/2^k) log(n/2^k), so the level total is n log(n/2^k). Summing over k from 0 to log₂ n gives n(Σ log n − Σ k) with the second sum equal to (log n)(log n + 1)/2, and the total is Θ(n log² n), matching the extended case 2. Carrying the same computation symbolically for f(n) ∝ n^q reproduces all three cases at once: the level totals form a constant, a growing, or a shrinking geometric series according as q < p, q = p, or q > p.

Tree reasoning also handles the situations the theorem does not: uneven splits, recurrences with more than one recursive term of different shapes, and recurrences whose base case is reached at an input size that is not a constant. Such a recurrence is not a master-theorem recurrence at all: the leaves do not disappear with depth, and the cost has to be attributed back to the level at which the recursion stops. The same accounting shows up wherever recursion is turned into iteration, and the amortized bookkeeping in dynamic arrays is a special case of it: a total over a sequence, obtained by summing a geometric series rather than solving a recurrence.