Hands-On Recurrences

The Story That Explains the Master Theorem

Most divide-and-conquer algorithms — merge sort, binary search, Karatsuba multiplication, Strassen's matrix product — describe their running time with a recurrence of the same shape. The Master Theorem (Chapter 4 of Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms) is a recipe that reads that shape and hands you a tight Θ-bound without any algebra.

Anatomy of a Recurrence

The Master Theorem applies to recurrences of exactly this form, where a ≥ 1 and b > 1 are constants and f(n) is asymptotically positive:

Three Ways to Solve a Recurrence

CLRS gives three tools. The Master Theorem is the fastest, but it grew out of the recursion-tree picture — understanding that picture is what makes the theorem stop feeling like memorisation.

The Recursion Tree — Where the Theorem Comes From

Picture merge sort: T(n) = 2T(n/2) + cn. Each node does cn work to merge, then splits into two half-sized children. Watch what the cost does at each level. The animated dot below traces the running total as we sweep down the tree.

The Master Theorem — The Three Cases

Let p = logba. Compare f(n) with the watershed np. Exactly one of three things is true, and each gives a tight bound.

The same three cases, viewed as a contest between two stacks of work:

A 4-Step Recipe for Applying the Theorem

Worked Example 1 — Merge Sort (Case 2)

Worked Example 2 — T(n) = 9T(n/3) + n (Case 1)

This is the textbook Case-1 example from CLRS.

Worked Example 3 — T(n) = 3T(n/4) + n log n (Case 3)

Case 3 is the only one with a second hoop: the regularity condition. Here is the full check, also straight from CLRS.

A Cheat Sheet of Common Recurrences

Python — A Master Theorem Solver

Here is a compact solver that classifies the case and reports the Θ-bound for any recurrence whose f(n) has the form n^e·(log n)^k.

from math import log, isclose

def master_theorem(a, b, f_exp, f_log=0):
    """Solve T(n) = a*T(n/b) + f(n), where f(n) = n^f_exp * (log n)^f_log."""
    assert a >= 1 and b > 1, "Master Theorem needs a >= 1 and b > 1"

    crit = log(a) / log(b)              # watershed exponent p = log_b(a)

    if f_exp < crit:                       # f(n) smaller -> leaves dominate
        return f"Case 1  ->  Theta(n^{crit:.4g})"

    elif isclose(f_exp, crit):             # tie -> one extra log factor
        k = f_log + 1
        return f"Case 2  ->  Theta(n^{crit:.4g} * log^{k} n)"

    else:                                  # f(n) larger -> root dominates
        return f"Case 3  ->  Theta(f(n))   [verify regularity!]"


# (name, a, b, exponent of n in f(n), power of log in f(n))
tests = [
    ("Merge Sort",    2, 2, 1, 0),
    ("Binary Search", 1, 2, 0, 0),
    ("Case 1 (CLRS)", 9, 3, 1, 0),
    ("Strassen",      7, 2, 2, 0),
    ("Case 3 (CLRS)", 3, 4, 1, 1),
]

for name, a, b, fe, fl in tests:
    print(f"{name:14s}: {master_theorem(a, b, fe, fl)}")

Proving Case 2 by Summing the Tree

This second snippet makes the recursion-tree picture concrete: it prints the work at every level for merge sort. Watch how every line lands on the same number — that's Case 2.

from math import log

def level_costs(a, b, n, f):
    """Print the work done at each level of the recursion tree."""
    depth = int(log(n, b))              # tree height = log_b(n)
    total = 0
    for i in range(depth + 1):
        nodes = a ** i                    # a^i nodes at level i
        size  = n / (b ** i)              # each subproblem has size n / b^i
        cost  = nodes * f(size)           # work at this level
        total += cost
        print(f"  level {i:2d}: {nodes:>6} nodes x f(n/{b**i:<4}) = {cost:,.0f}")
    print(f"  TOTAL work across the tree ~ {total:,.0f}")
    return total

# Merge sort: T(n) = 2T(n/2) + n, with n = 1024
level_costs(2, 2, 1024, lambda x: x)

When the Master Theorem Fails

The theorem is powerful but not universal. CLRS is explicit that gaps exist between the cases, and that some recurrences don't fit the form at all.

The Three Methods Compared

Golden Rules