The Master Theorem, Explained

The master theorem is a formula for finding the time complexity of a divide-and-conquer algorithm directly from its recurrence relation, without expanding a recursion tree by hand. Many divide-and-conquer algorithms — merge sort, binary search, the classic recursive multiplication algorithms — produce a recurrence of the same general shape, and the master theorem classifies that shape into one of three cases, each with a known closed-form answer.

The recurrence it applies to

The master theorem covers recurrences of the form:

T(n) = a·T(n/b) + f(n)

where:

• a is the number of subproblems the algorithm recurses into (must be ≥ 1)
• b is the factor by which the problem size shrinks each time (must be > 1)
• f(n) is the cost of the work done outside the recursive calls — combining results, splitting the input, or any other per-call overhead

Merge sort, for example, recurses into 2 subproblems (a = 2), each half the size of the original (b = 2), and does O(n) work to merge the two sorted halves back together (f(n) = n). That gives T(n) = 2T(n/2) + n — the textbook case the master theorem was built to handle.

The three cases

The theorem compares f(n) — the cost outside the recursion — against n^(log_b a), which represents the total cost of all the work done purely by recursing, ignoring f(n) entirely. Whichever of the two dominates determines the overall running time.

Case 1 — the recursion dominates. If f(n) grows polynomially slower than n^(log_b a), the cost is dominated by the sheer number of recursive calls, and:

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

Case 2 — the two are balanced. If f(n) grows at the same rate as n^(log_b a) (formally, f(n) = Θ(n^(log_b a) · log^k n) for some k ≥ 0), the recursion and the per-call work contribute comparably, and an extra logarithmic factor appears:

T(n) = Θ(n^(log_b a) · log^(k+1) n)

The common special case is k = 0, giving T(n) = Θ(n^(log_b a) · log n) — this is the merge sort case.

Case 3 — the combine step dominates. If f(n) grows polynomially faster than n^(log_b a), and a technical condition called the regularity condition holds (a·f(n/b) ≤ c·f(n) for some c < 1 and large n), the per-call work dominates the recursion entirely, and:

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

Working through merge sort

T(n) = 2T(n/2) + n, so a = 2, b = 2, f(n) = n.

Compute n^(log_b a) = n^(log_2 2) = n^1 = n.

f(n) = n grows at exactly the same rate as n^(log_b a) = n, with k = 0 — that’s case 2. So:

T(n) = Θ(n log n)

This matches the well-known result for merge sort without needing to draw out the recursion tree level by level and sum the costs manually.

Working through binary search

T(n) = T(n/2) + O(1), so a = 1, b = 2, f(n) = O(1) (constant work per call — just a comparison).

Compute n^(log_b a) = n^(log_2 1) = n^0 = 1.

f(n) = O(1) matches n^(log_b a) = 1 with k = 0 — again case 2:

T(n) = Θ(1 · log n) = Θ(log n)

Which is exactly the binary search result every introductory algorithms course teaches, derived here from the same general-purpose formula rather than a search-specific argument.

Where the master theorem doesn’t apply

The theorem is a convenience, not a universal tool — it only applies to recurrences of the exact form T(n) = a·T(n/b) + f(n), with constant a and b. Several common patterns fall outside that shape:

• Unequal subproblem sizes, like T(n) = T(n/3) + T(2n/3) + n, where the subproblems aren’t all the same fraction of n.
• Subtractive recurrences, like T(n) = T(n-1) + n, common in some recursion vs. iteration comparisons, where the problem shrinks by a constant amount rather than a constant factor.
• f(n) that doesn’t cleanly fall into one of the three cases — for instance, f(n) = n / log n, which sits in a gap between case 1 and case 2 that the basic theorem doesn’t cover without extended versions.

For these, other techniques apply: the recursion-tree method, the substitution method (guess a bound, then prove it by induction), or the more general Akra-Bazzi method, which handles unequal subproblem sizes that the master theorem can’t.

Why it’s useful beyond the exam

Divide-and-conquer shows up constantly in real systems, not just textbook sorting algorithms — from greedy and dynamic-programming alternatives to tree-based data structures like binary search trees, a huge share of practical algorithm design reduces to some variant of “split, recurse, combine.” Recognizing the a, b, and f(n) in a new recurrence and reaching for the master theorem is usually far faster than re-deriving a recursion tree from scratch every time, and it gives a quick sanity check on whether a proposed algorithm’s asymptotic behavior is what its design suggests it should be.

The takeaway

The master theorem turns a divide-and-conquer recurrence of the form T(n) = a·T(n/b) + f(n) into a direct answer by comparing f(n) against n^(log_b a): whichever term dominates sets the overall time complexity, with a balanced middle case picking up an extra logarithmic factor. It covers a large share of practical divide-and-conquer algorithms, but recurrences with unequal subproblem sizes or unusual f(n) still need the recursion-tree or substitution methods it was designed to replace.