The Master Theorem

Analogy categoryAnalogies

Introduction

The Master Theorem is a formula for directly determining the asymptotic running time of recurrences of the form T(n) = aT(n/b) + f(n), where a >= 1 is the number of subproblems, b > 1 is the factor by which the problem size shrinks, and f(n) is the cost of work done outside the recursive calls. Instead of building a recursion tree by hand every time, the Master Theorem compares f(n) against n^(log_b a), the 'watershed' function, and immediately tells you which term dominates the total running time.

🏏

Cricket analogy: The Master Theorem is like a quick formula for predicting a run chase's outcome from the number of partnerships (a), how much the target shrinks each partnership (b), and the runs scored outside partnerships f(n), without simulating every over.

Explanation

Let n0 = n^(log_b a). The Master Theorem has three cases. Case 1: if f(n) = O(n^(log_b a - eps)) for some constant eps > 0 (f(n) grows polynomially slower than n0), then T(n) = Theta(n^(log_b a)) — the recursive work dominates. Case 2: if f(n) = Theta(n^(log_b a) * log^k n) for some k >= 0 (f(n) grows at about the same rate as n0, possibly with a log factor), then T(n) = Theta(n^(log_b a) * log^(k+1) n) — the most common instance is k=0, giving T(n) = Theta(n0 * log n). Case 3: if f(n) = Omega(n^(log_b a + eps)) for some eps > 0 (f(n) grows polynomially faster than n0) AND the regularity condition a*f(n/b) <= c*f(n) holds for some c < 1 and large n, then T(n) = Theta(f(n)) — the combine work dominates.

🏏

Cricket analogy: Case 1 is when the sheer number of partnerships, the recursive work, outpaces any single big over f(n), so the innings total is dominated by partnership count; Case 2 is when both grow together in balance; Case 3 is when one explosive over f(n) outweighs everything else, dominating the total.

Example

python

import math

def classify_recurrence(a, b, f_growth_exponent):
    """Illustrates comparing f(n) = n^f_growth_exponent against n^(log_b a)."""
    watershed_exponent = math.log(a, b)  # exponent of n^(log_b a)
    if f_growth_exponent < watershed_exponent:
        return "Case 1: T(n) = Theta(n^log_b(a))"
    elif math.isclose(f_growth_exponent, watershed_exponent):
        return "Case 2: T(n) = Theta(n^log_b(a) * log n)"
    else:
        return "Case 3: T(n) = Theta(f(n))  [regularity condition must also hold]"


# Case 1: T(n) = 8T(n/2) + n^2   -> a=8, b=2, f(n)=n^2
# log_b(a) = log2(8) = 3; f_growth_exponent = 2 < 3
print(classify_recurrence(8, 2, 2))

# Case 2: T(n) = 2T(n/2) + n  (merge sort) -> a=2, b=2, f(n)=n
# log_b(a) = log2(2) = 1; f_growth_exponent = 1 == 1
print(classify_recurrence(2, 2, 1))

# Case 3: T(n) = T(n/2) + n^2  -> a=1, b=2, f(n)=n^2
# log_b(a) = log2(1) = 0; f_growth_exponent = 2 > 0
print(classify_recurrence(1, 2, 2))

Analysis

Worked example for each case. Case 1 — T(n) = 8T(n/2) + n^2: here a=8, b=2, so n^(log_b a) = n^(log2 8) = n^3. Since f(n) = n^2 = O(n^(3-eps)) for eps=1, Case 1 applies and T(n) = Theta(n^3); the recursive subdivision dominates over the quadratic combine cost. Case 2 — T(n) = 2T(n/2) + n (merge sort): a=2, b=2, so n^(log_b a) = n^1 = n. Since f(n) = n = Theta(n^1 * log^0 n), Case 2 applies with k=0, giving T(n) = Theta(n log n), matching the recursion-tree derivation. Case 3 — T(n) = T(n/2) + n^2: a=1, b=2, so n^(log_b a) = n^0 = 1. Since f(n) = n^2 = Omega(n^(0+eps)) for eps=2, and the regularity condition a*f(n/b) = 1*(n/2)^2 = n^2/4 <= (1/2)*n^2 = c*f(n) holds for c=1/2, Case 3 applies and T(n) = Theta(n^2); the top-level combine work dominates.

🏏

Cricket analogy: Splitting a squad of 8 sub-groups each half size with an added quadratic drill cost, Case 1, means the sheer number of sub-groups dominates; splitting into 2 halves with linear scoring work, Case 2 like merge sort, balances evenly; splitting into 1 half with a heavy quadratic finals ceremony, Case 3, means that one event dominates everything.

Key Takeaways

The Master Theorem solves T(n) = aT(n/b) + f(n) by comparing f(n) to the watershed function n^(log_b a).
Case 1 (f(n) polynomially smaller): T(n) = Theta(n^(log_b a)) — recursion dominates, e.g. T(n)=8T(n/2)+n^2 gives Theta(n^3).
Case 2 (f(n) about equal): T(n) = Theta(n^(log_b a) log^(k+1) n) — balanced, e.g. merge sort gives Theta(n log n).
Case 3 (f(n) polynomially larger, regularity holds): T(n) = Theta(f(n)) — combine step dominates, e.g. T(n)=T(n/2)+n^2 gives Theta(n^2).
The Master Theorem does not apply when a < 1, when f(n) is not polynomial (e.g. it is exponential or n/log n), or when subproblem sizes are unequal — a recursion tree or the Akra-Bazzi method is needed instead.

Practice what you learned

1. For T(n) = 8T(n/2) + n^2, what is n^(log_b a) and which Master Theorem case applies?

2. For merge sort's recurrence T(n) = 2T(n/2) + n, which Master Theorem case applies and what is the result?

3. In Case 3 of the Master Theorem, besides f(n) being polynomially larger than n^(log_b a), what additional condition must hold?

4. For T(n) = T(n/2) + n^2, what does the Master Theorem conclude?

Was this page helpful?

Recursion Trees and Recurrence Relations

Recursion vs Iteration

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#TheMasterTheorem#Master#Theorem#Explanation#Example#StudyNotes#SkillVeris