Divide-and-conquer algorithms like merge sort, binary search, and quick sort all lead to a recurrence of the same shape:

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

You could solve it by expanding it by hand or drawing a recursion tree, but for this family of recurrences there's a much faster path.

The Master Theorem is a formula that reads the Big O of most divide-and-conquer recurrences straight off their structure, with no expansion or induction.

The Master Theorem applies to recurrences of the form:

T(n) = aT(n/b) + f(n)

Where:

The whole point is to find the asymptotic complexity directly, without expanding the recurrence by hand.

We analyze recurrences of the form:

Everything hinges on one quantity, the watershed:

This is the total work done at the bottom of the recursion tree. A tree that branches a ways and is log_b n levels deep has a^(log_b n) leaves, which equals n^(log_b a), and each leaf does constant work. So n^(log_b a) measures the recursive side of the cost, and the three cases all come down to comparing the combine work f(n) against it: is f(n) smaller, equal, or larger?

Case 1: Subproblem Work Dominates

Condition:

In words, the combine work f(n) grows polynomially slower than the recursive work n^(log_b a). The ε > 0 is what makes "slower" mean slower by a factor of some power of n, not just by a constant or a log.

Result:

Intuition: almost all the time is spent inside the recursion. The combine work is negligible by comparison, so the leaf work n^(log_b a) sets the complexity.

Example:

Here: a = 8, b = 2 → log₂8 = 3

Case 2: Both Parts Balance

Condition

The recursive work and the combine work grow at the same rate.

Result:

Intuition: every level of the recursion tree does roughly the same amount of work, and there are log n levels, so the total is that per-level work times log n.

Example:

Here:

Case 3: Outside Work Dominates

If

and the regularity condition a × f(n/b) ≤ c × f(n) holds for some constant c < 1 and all sufficiently large n,

then:

Intuition: the combine step f(n) does so much work that the recursive calls become insignificant, so f(n) sets the complexity. The regularity condition rules out oddly behaved f(n) and guarantees the top-level cost keeps dominating all the way down.

Example:

Here:

Example 1: Binary Search

The watershed is:

So f(n) = Θ(1) = Θ(n⁰), which matches the watershed → Case 2: T(n) = Θ(log n)

Example 2: Merge Sort

The watershed is:

So f(n) = Θ(n¹), which matches the watershed → Case 2: T(n) = Θ(n log n)

Example 3: Tower of Hanoi

This isn't in Master Theorem form: the subproblem size is n−1, not n/b. The input shrinks by subtraction, not division, so there's no b to work with and the theorem doesn't apply.

Expanding it by hand instead gives T(n) = 1 + 2 + 4 + ... + 2^(n−1), which is Θ(2ⁿ).

Example 4: Strassen’s Matrix Multiplication

Here:

This is how Strassen’s algorithm beats the classic O(n³) approach.

Example 5: Many Subproblems, Cheap Combine

Even though the combine step is linear, the recursion spawns so many subproblems that the leaf work n² swamps it.

The master theorem is widely applicable but not universal. It assumes a specific shape: equal-sized subproblems, a division-based split, and an f(n) that is polynomially comparable to the watershed n^(log_b a). It breaks down when any of those assumptions is violated.

You cannot use it when:

In these cases, fall back to the recursion tree or substitution methods from the previous chapter.

For most divide-and-conquer recurrences, the Master Theorem lets you read off the complexity in one step, without drawing a recursion tree or running induction. For the cases where it does not apply, the substitution and recursion-tree methods from the previous chapter fill the gap.

Together with Big O notation, best/worst/average case analysis, amortized analysis, and recurrence relations, this completes the foundation for reasoning about how any algorithm scales as input grows.