Imagine having a single formula that could solve virtually any divide-and-conquer recurrence instantly. No recursion tree drawing, no tedious expansion, no guessing—just plug in the parameters and read off the answer.

That tool exists. It's called the Master Theorem, and it's one of the most powerful results in algorithm analysis. Once you internalize it, you'll be able to analyze the complexity of any D&C algorithm in seconds.

The Master Theorem provides asymptotic solutions for recurrences of the form:

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

Where:

• a ≥ 1: Number of subproblems in each recursion
• b > 1: Factor by which the input size is reduced
• f(n): Cost of the work done outside the recursive calls (divide + combine)

The Three Cases:

Let c_crit = log_b(a). This is the critical exponent. The solution depends on how f(n) compares to n^{c_crit}:

Case 1: f(n) = O(n^c) where c < c_crit

T(n) = Θ(n^{c_crit}) = Θ(n^{log_b a})

The recursive work dominates. Leaves of the recursion tree control the complexity.

Case 2: f(n) = Θ(n^{c_crit} × log^k n) for k ≥ 0

T(n) = Θ(n^{c_crit} × log^{k+1} n)

Balanced: the work is evenly distributed across levels.

Case 3: f(n) = Ω(n^c) where c > c_crit, AND the regularity condition holds

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

The non-recursive work dominates. The root of the tree controls the complexity.

The critical exponent c_crit = log_b(a) is the key to the Master Theorem. It represents the rate at which the number of subproblems grows as we descend the recursion tree.

What c_crit Tells Us:

• The total number of leaves in the recursion tree is n^{c_crit}
• If each leaf does O(1) work, the leaves contribute Θ(n^{c_crit}) total work
• This is the "baseline" complexity that the non-recursive work f(n) must compete against

Deriving the Critical Exponent:

Let's see why leaves contribute n^{log_b a} work:

1. Tree depth: log_b(n) levels (from n down to 1)
2. Branching factor: Each node has a children
3. Number of leaves: a^{depth} = a^{log_b n} = n^{log_b a}

The identity a^{log_b n} = n^{log_b a} is key:

a^{log_b n} = a^{(log_a n / log_a b)}
           = (a^{log_a n})^{1/log_a b}
           = n^{1/log_a b}
           = n^{log_b a}

When This Applies:

Case 1 applies when the non-recursive work f(n) grows slower than the leaf count n^{log_b a}. The explosive growth of subproblems overwhelms the divide/combine work.

Solution:

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

Example 1: T(n) = 2T(n/2) + O(1)

• a = 2, b = 2, f(n) = O(1) = O(n⁰)
• c_crit = log₂(2) = 1
• Compare: c = 0 < 1 = c_crit ✓ Case 1
• Solution: T(n) = Θ(n¹) = Θ(n)

This is the D&C max/min pattern. O(1) work per node, n leaves.

Example 2: T(n) = 8T(n/2) + O(n²)

• a = 8, b = 2, f(n) = O(n²)
• c_crit = log₂(8) = 3
• Compare: c = 2 < 3 = c_crit ✓ Case 1
• Solution: T(n) = Θ(n³)

This is naive D&C matrix multiplication. 8 subproblems of n/2 each, with O(n²) combine (the additions). The 8 recursive calls dominate.

Example 3: T(n) = 7T(n/2) + O(n²)

• a = 7, b = 2, f(n) = O(n²)
• c_crit = log₂(7) ≈ 2.807
• Compare: c = 2 < 2.807 = c_crit ✓ Case 1
• Solution: T(n) = Θ(n^{log₂ 7}) ≈ Θ(n^{2.807})

Strassen's algorithm. Reducing from 8 to 7 subproblems drops complexity from n³ to n^{2.807}.

When This Applies:

Case 2 applies when f(n) grows at exactly the same rate as the leaf count, possibly with logarithmic factors. Each level of the tree contributes roughly equal work.

Solution:

T(n) = Θ(n^{log_b a} × log^{k+1} n)

The most common subcase is k = 0: f(n) = Θ(n^{log_b a}), giving T(n) = Θ(n^{log_b a} log n).

Example 1: T(n) = 2T(n/2) + O(n) — The Classic

• a = 2, b = 2, f(n) = Θ(n)
• c_crit = log₂(2) = 1
• f(n) = Θ(n¹) = Θ(n^{c_crit}) ✓ Case 2 with k = 0
• Solution: T(n) = Θ(n log n)

The merge sort recurrence. Every level does O(n) work, and there are O(log n) levels.

Example 2: T(n) = T(n/2) + O(1)

• a = 1, b = 2, f(n) = Θ(1)
• c_crit = log₂(1) = 0
• f(n) = Θ(1) = Θ(n⁰) = Θ(n^{c_crit}) ✓ Case 2 with k = 0
• Solution: T(n) = Θ(log n)

Binary search. O(1) work per level × O(log n) levels.

Note: Some textbooks list this as base case of Case 2; others as a special case.

Example 3: T(n) = 4T(n/2) + O(n² log n) — Extended Case 2

• a = 4, b = 2, f(n) = Θ(n² log n)
• c_crit = log₂(4) = 2
• f(n) = Θ(n² log n) = Θ(n^{c_crit} × log¹ n) ✓ Case 2 with k = 1
• Solution: T(n) = Θ(n² log² n)

When f(n) has a log factor, it carries through with an extra power.

When This Applies:

Case 3 applies when the non-recursive work f(n) grows faster than the leaf count. The work at the root level dominates all recursive contributions.

Solution:

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

Important: The Regularity Condition

Case 3 comes with a requirement: f(n) must satisfy the regularity condition:

a × f(n/b) ≤ c × f(n) for some c < 1 and large n

This ensures that f(n) truly dominates—the work decreases sufficiently fast as we go down the tree.

Example 1: T(n) = T(n/2) + O(n)

• a = 1, b = 2, f(n) = Θ(n)
• c_crit = log₂(1) = 0
• Compare: c = 1 > 0 = c_crit ✓ Case 3 applies
• Regularity: 1 × f(n/2) = n/2 = (1/2) × n = (1/2) × f(n) ✓ (c = 1/2)
• Solution: T(n) = Θ(n)

The quickselect average case. O(n) partitioning at the top level, then recurse on half. The work halves each level, so total is O(n).

Example 2: T(n) = 2T(n/2) + O(n²)

• a = 2, b = 2, f(n) = Θ(n²)
• c_crit = log₂(2) = 1
• Compare: c = 2 > 1 = c_crit ✓ Case 3 applies
• Regularity: 2 × f(n/2) = 2 × (n/2)² = n²/2 = (1/2) × f(n) ✓
• Solution: T(n) = Θ(n²)

A hypothetical algorithm with quadratic combine. The root's O(n²) work dominates the O(n) leaf contributions.

Example 3: T(n) = 3T(n/4) + O(n log n)

• a = 3, b = 4, f(n) = Θ(n log n)
• c_crit = log₄(3) ≈ 0.792
• Compare: f(n) = Θ(n log n) vs n^{0.792}
• n log n grows faster than n^{0.792} for large n ✓ Case 3
• Regularity check: 3 × ((n/4) log(n/4)) ≈ (3/4) × n log n ✓ (c = 3/4)
• Solution: T(n) = Θ(n log n)

Here's the systematic procedure for applying the Master Theorem to any recurrence:

Worked Example: T(n) = 9T(n/3) + n

Step 1: a = 9, b = 3, f(n) = n

Step 2: c_crit = log₃(9) = 2

Step 3: f(n) = n = n¹, so c = 1

Step 4: Compare: c = 1 < 2 = c_crit → Case 1

Step 5: No regularity check needed for Case 1

Step 6: T(n) = Θ(n^{log₃ 9}) = Θ(n²)

Worked Example: T(n) = T(2n/3) + 1

Step 1: a = 1, b = 3/2, f(n) = 1

Step 2: c_crit = log_{3/2}(1) = 0

Step 3: f(n) = 1 = n⁰, so c = 0

Step 4: Compare: c = 0 = 0 = c_crit → Case 2 (k = 0)

Step 5: Case 2 applies directly

Step 6: T(n) = Θ(n⁰ × log n) = Θ(log n)

The Master Theorem is powerful but not universal. Here are the cases where it doesn't apply:

1. Unequal Subproblem Sizes

The Master Theorem requires all subproblems to have the same size n/b.

T(n) = T(n/3) + T(2n/3) + n    ✗ Can't apply Master Theorem

Solution: Use the Akra-Bazzi theorem (generalization) or the recursion tree method.

This recurrence (randomized quicksort partition) solves to O(n log n) via other methods.

2. Non-Polynomial f(n)

The Master Theorem assumes f(n) has polynomial growth. Functions like 2ⁿ, n!, or even n/log n don't fit the standard cases.

T(n) = 2T(n/2) + 2ⁿ    ✗ f(n) is exponential
T(n) = 2T(n/2) + n/log n    ✗ Falls between cases

Solution: Use recursion trees or generating functions for unusual f(n).

3. Non-Constant a or b

If the number of subproblems or the division factor varies with n, the Master Theorem doesn't apply.

T(n) = T(√n) + 1    ✗ Division factor is √n, not constant
T(n) = nT(n/2) + 1    ✗ Number of subproblems varies with n

Solution: Substitution or recursion tree analysis.

Note: T(n) = T(√n) + 1 can be solved by substituting m = log n.

4. Gap Between Cases 1 and 2, or 2 and 3

The Master Theorem has gaps when f(n) = Θ(n^{c_crit} / log^k n) for k > 0.

T(n) = 2T(n/2) + n/log n    ✗ Between Case 1 and Case 2

Solution: Extended Master Theorem variants or direct analysis.

Here's everything you need to apply the Master Theorem in one place:

The Recurrence Form:

T(n) = aT(n/b) + f(n)    where a ≥ 1, b > 1

The Critical Exponent:

c_crit = log_b(a)

The Three Cases:

What's Next:

You now have the formal machinery to solve D&C recurrences. The next page develops intuition—understanding why these results are true without formal proofs, so you can reason about recurrences even when you don't remember the exact formulas.