The master theorem is a result in the analysis of algorithms that gives asymptotically tight bounds for many recurrence relations of the form
Such recurrences commonly describe the time complexity of divide-and-conquer algorithms: a problem of size produces smaller problems, each of size , while represents the work done outside the recursive calls. The theorem compares with , the growth associated with the recursive branching, and identifies whether the total cost is dominated by small subproblems, distributed across recursion levels, or dominated by work near the original problem.
Recurrence model and assumptions
In the standard formulation:
- is a constant representing the number of recursive subproblems.
- is a constant representing the reduction in problem size.
- is an asymptotically nonnegative function describing nonrecursive work, including splitting, combining, and other overhead.
- for input sizes below a fixed positive threshold.
In an algorithm, is normally an integer, although the mathematical recurrence can be studied for real .
The notation , , and belongs to asymptotic notation. Respectively, these express an asymptotic upper bound, lower bound, and matching upper and lower bounds, up to constant factors.
For a clean statement, may be restricted to powers of , so that repeated division reaches the base case exactly. Algorithmic recurrences often instead use floors or ceilings, such as
These rounding changes preserve the usual bounds under standard regularity assumptions, but an arbitrary recurrence with irregular costs should not be treated as automatically equivalent to the unrounded version.
The theorem applies to the recurrence that has actually been established. An inequality such as
can support an upper bound, but does not by itself establish a matching lower bound.
Standard three-case theorem
Define the critical exponent
The simplest standard version has three cases.
Case 1: Recursive branching dominates
If there exists a constant such that
then
Here is smaller than by a polynomial factor. The work near the leaves of the recursion dominates the total.
For example,
Since , and ,
Case 2: Work is balanced across levels
If
then
Each recursion level contributes the same asymptotic amount of work, and there are levels.
A frequently taught extension includes logarithmic factors: if
for a constant , then
For instance,
has and , giving
Case 3: Nonrecursive work dominates
If there exists a constant such that
and there exists a constant such that, for all sufficiently large ,
then
The second condition is the regularity condition. It ensures that the combined nonrecursive work decreases geometrically as the recursion descends. A polynomial lower bound on alone does not guarantee this behavior for an irregular function.
For example,
Here , and
Thus the regularity condition holds with , and
Why the theorem works
The theorem can be understood using a recursion tree, which represents the calls made by a recursive computation.
For simplicity, let , and stop the recurrence at size . At depth :
- there are subproblems;
- each subproblem has size ;
- the total nonrecursive work is .
Expanding the recurrence gives
Because ,
The leaves therefore contribute .
If , then the cost at level is
The resulting geometric series has three possible behaviors:
- If , its terms grow with depth, so the bottom levels dominate.
- If , its terms have equal asymptotic size, adding a logarithmic factor.
- If , its terms decrease with depth, so the top levels dominate.
The theorem generalizes this comparison beyond exact power functions.
Applications
Binary search
The usual worst-case recurrence for binary search is
Here , , and . The nonrecursive work matches , so Case 2 gives
Merge sort
Merge sort recursively sorts two approximately equal halves and merges them in linear time:
Since , Case 2 yields
Classical recursive matrix multiplication
A direct recursive method for multiplying two square matrices performs eight multiplications on half-sized matrices, together with quadratic addition work:
Here , so Case 1 gives
This recurrence describes that particular method, not a lower bound for every matrix multiplication algorithm.
Logarithmic boundary cases
The polynomial-gap requirements in Cases 1 and 3 are essential. A function can be smaller or larger than without differing from it by a polynomial factor.
For example,
with a constant-size cutoff above , does not fit any of the three basic cases:
- is not polynomially smaller than ;
- it is not ;
- it is not polynomially larger than .
Its solution is
A broader logarithmic extension handles
for any fixed real . Under the same constant-size base-case assumptions,
These bounds follow by summing the level costs; they extend, rather than contradict, the basic theorem.
Limitations and related methods
The master theorem is not a universal method for solving recurrences. Its standard form does not directly cover:
Unequal subproblem sizes, such as
Subtractive size reductions, such as
A nonconstant number of recursive calls or size reductions that depend on .
Irregular toll functions that fail the required comparisons or regularity condition.
Recurrences involving many possible partition sizes, such as the expected-time recurrence for quicksort.
The Akra–Bazzi theorem handles a broader class of divide-and-conquer recurrences, including many with unequal subproblem sizes. Other approaches include repeated expansion, recursion-tree summation, and proving a proposed bound by induction.
The master theorem measures the resource represented by ; it does not determine that resource automatically. In particular, adding the costs of recursive calls models total work, not necessarily elapsed time in parallel computing. Likewise, the running-time recurrence does not directly determine space complexity, because recursive subproblems may execute sequentially and reuse memory.