The Master Theorem

The Master theorem gives asymptotic bounds for recurrences of the form T(n) = aT(n/b) + f(n). A recursive call creates a subproblems, each with input size n/b, while f(n) measures the work performed outside those calls.

The parameters must be constants with a ≥ 1 and b > 1. The theorem applies to equal-size divide-and-conquer recurrences, a narrower family than the general recurrence relations used in algorithm analysis.

The expression n^(log_b a) is the theorem's comparison term. A recursion tree has a^i nodes at level i and reaches its leaves after log_b n levels. Substituting the depth gives a^(log_b n) = n^(log_b a) leaves.

Compare f(n) with this term using asymptotic bounds. The relative growth rates identify whether the recursive population, the accumulated work across levels, or the root-side work controls the total.

At level i, the tree contains a^i subproblems of size n/b^i. Its non-recursive work is therefore a^i f(n/b^i). Summing these level costs and adding the leaves produces the recurrence's total cost.

The three theorem cases describe three geometric shapes. Level costs can grow toward the leaves, remain comparable, or shrink toward the leaves. The Master theorem packages those sums into reusable conditions.

Case one applies when f(n) = O(n^(log_b a − ε)) for some constant ε > 0. The local work is polynomially smaller than the critical term, so level costs grow as the recursion expands.

The leaves dominate the sum and T(n) = Θ(n^(log_b a)). For T(n) = 4T(n/2) + n, the critical term is n²; linear local work is polynomially smaller, giving Θ(n²).

In the basic second case, f(n) = Θ(n^(log_b a)). Every level contributes the same asymptotic amount, and the recursion tree contains Θ(log n) levels.

The result is T(n) = Θ(n^(log_b a) log n). Merge sort has a = 2, b = 2, and f(n) = Θ(n). Its critical term is also n, so the total is Θ(n log n).

A common extended form of case two handles f(n) = Θ(n^(log_b a) log^k n) for fixed k ≥ 0. Summing across the recursion levels adds one logarithmic power.

The solution becomes Θ(n^(log_b a) log^(k+1) n). The exact statement depends on the version of the theorem being used; conditions for negative k and other slowly varying factors require additional cases.

Case three applies when f(n) = Ω(n^(log_b a + ε)) for some ε > 0, subject to a regularity condition. The non-recursive work is polynomially larger than the critical term, so level costs decrease down the tree.

The upper levels dominate and T(n) = Θ(f(n)). For T(n) = 2T(n/2) + n², the critical term is n, while n² is polynomially larger. The solution is Θ(n²).

Case three also requires a f(n/b) ≤ c f(n) for some constant c < 1 and sufficiently large n. This condition ensures that total local work contracts by a fixed factor from one level to the next.

Polynomial growth usually satisfies the condition, but an irregular function can be asymptotically large without contracting consistently. Omitting this check turns the case-three mnemonic into an invalid proof.

Merge sort divides an input into two halves, recursively sorts each half, and merges the results in linear time. Its recurrence is T(n) = 2T(n/2) + Θ(n).

Here n^(log₂ 2) = n, matching the merge cost. Case two gives Θ(n log n) worst-case time. The theorem determines the growth rate; stability and auxiliary memory require separate analysis.

Binary search retains one half of the search interval and performs constant work to compare the midpoint. Its recurrence is T(n) = T(n/2) + Θ(1).

With a = 1 and b = 2, the critical term is n^(log₂ 1) = 1. Case two gives Θ(log n) worst-case comparisons. An iterative implementation has the same time bound with constant auxiliary space.

The standard theorem does not cover unequal subproblem sizes such as T(n) = T(n/3) + T(2n/3) + n, decrementing recurrences such as T(n) = T(n − 1) + n, or a non-constant number of recursive calls.

It also requires a polynomial separation in cases one and three. A local term such as n / log n can sit between the standard cases. Floors and ceilings are often harmless, but their treatment belongs to the theorem's formal conditions.

Use expansion or a recursion tree when the level sum is easy to expose. Use substitution to prove a candidate bound. The Akra–Bazzi method handles many unequal divide-and-conquer splits, while characteristic equations handle linear recurrences with constant coefficients.

The selection rule follows the recurrence's structure. The Master theorem is a specialized shortcut, not a definition of recursive complexity and not a replacement for checking the equation.

For T(n) = aT(n/b) + f(n), compare local work with n^(log_b a). Polynomially smaller work produces a leaf-dominated bound; matching work adds a logarithmic factor; polynomially larger regular work produces a root-dominated bound.

The theorem applies only when its form and side conditions hold. Recursion trees, substitution, and more general recurrence theorems remain necessary for equations outside that family.