Master TheoremSolving recurrences

01Why it exists

Reach for it when you see:T(n) = aT(n/b) + f(n), how many pieces you split into, how much smaller each piece is, recursion trees, the complexity of a divide-and-conquer algorithm.

02The core idea

The running time of a divide-and-conquer algorithm always has the same shape: T(n) = a·T(n/b) + f(n). Here a is how many subproblems you split into, b is how much smaller each subproblem is, and f(n) is the cost of splitting and merging. This lesson only covers the polynomial case f(n) = Θ(n^d), which already accounts for the overwhelming majority of the divide-and-conquer you will meet.

Picture the recursion tree. Level i holds a^i subproblems of size n/b^i, so the total work on level i is a^i × (n/b^i)^d = n^d × (a/b^d)^i. That is a geometric series with ratio r = a/b^d, and the sum of a geometric series is decided by its ratio: when r is greater than 1 the last term is the largest, when r equals 1 every term is the same, and when r is less than 1 the first term is the largest. That is where the three cases come from.

Comparing log_b a (the exponent on the leaf count) with d (the exponent on the work at the root) is the same as comparing r with 1. Case 1: log_b a > d, the leaves dominate and T(n) = Θ(n^(log_b a)) — Strassen's n^2.81, for example. Case 2: log_b a = d, every level does n^d work across log n levels, so T(n) = Θ(n^d log n) — merge sort's n log n, or binary search's log n. Case 3: log_b a < d, the root dominates and T(n) = Θ(n^d), as in an algorithm that halves the input but spends n² merging, where the recursion buys you nothing at all.

The usual misconception is that anything that halves must be log n. Halving only guarantees that there are log n levels; the total time still depends on how much work each level does. The theorem also does not cover an f(n) that is not a polynomial (T(n) = 2T(n/2) + n log n, say, which falls between cases 2 and 3), subproblems that do not shrink by a constant factor (quicksort's worst case, T(n) = T(n−1) + n, which removes only one element at a time), or subproblems of different sizes (T(n) = T(n/3) + T(2n/3) + n). For those, go back to drawing the recursion tree, or use the substitution method.

03The algorithm

1. 1Read a (how many recursive calls), b (how much smaller the input to each call is) and d (the power of n in the work done outside the recursion) straight off the code.
2. 2Compute log_b a. It is 0 when a = 1, 1 when a = b, and 2 when a = b². Otherwise reach for a calculator: log₂ 7 ≈ 2.81, for instance.
3. 3Compare log_b a with d. Greater: case 1, the answer is Θ(n^(log_b a)). Equal: case 2, the answer is Θ(n^d log n). Less: case 3, the answer is Θ(n^d).
4. 4Sanity-check with the recursion tree: work out the cost of level 0, level 1 and level 2, and see whether it is growing, holding steady or shrinking. The direction has to match the case you picked.
5. 5If f(n) is not a plain polynomial, or the subproblems are not the same size, the theorem does not apply. Fall back to summing a recursion tree level by level, or guess the answer and verify it by induction.

04Interactive demo

Pick a familiar algorithm, or dial in your own a, b and d. The top shows the comparison and the conclusion; underneath is the work done on each level of the recursion tree. In case 1 the bars grow longer level by level, in case 2 they all have the same length, and in case 3 they shrink. Watch what fraction of the total the root level and the leaf level each account for.

05Code

The theorem is not an algorithm, so the code here is a small calculator: feed it a, b and d and it returns the case and the complexity, then sums a recursion tree level by level to check the result and show how much the total work grows when n doubles.

import math


def npow(d):
    """How to print n^d: n^0 prints as 1, n^1 prints as n"""
    return "1" if d == 0 else "n" if d == 1 else f"n^{d}"


def master(a, b, d):
    """Solve T(n) = a·T(n/b) + Θ(n^d). Returns (case, complexity string).
    Compare log_b(a) with d:
      greater → the leaves dominate, Θ(n^log_b a)
      equal   → every level does the same work, Θ(n^d · log n)
      less    → the root dominates, Θ(n^d)
    """
    e = math.log(a, b)                      # log_b a, the exponent on the leaf count
    if abs(e - d) < 1e-9:
        return 2, "Θ(log n)" if d == 0 else f"Θ({npow(d)} log n)"
    if e > d:
        return 1, f"Θ(n^{e:.2f})"
    return 3, f"Θ({npow(d)})"


# Sum the recursion tree level by level to check the answer the theorem gives
def recursion_tree(a, b, d, n):
    total, size, nodes = 0, n, 1
    while size >= 1:
        total += nodes * size ** d          # this level: nodes subproblems, each costing size^d
        nodes *= a
        size /= b
    return total


if __name__ == "__main__":
    for name, (a, b, d) in {
        "Merge sort": (2, 2, 1),
        "Binary search": (1, 2, 0),
        "Karatsuba": (3, 2, 1),
        "Strassen": (7, 2, 2),
    }.items():
        case, ans = master(a, b, d)
        print(f"{name}: T(n) = {'' if a == 1 else a}T(n/{b}) + {npow(d)} → case {case}, {ans}")
    # Merge sort: T(n) = 2T(n/2) + n → case 2, Θ(n log n)
    # Binary search: T(n) = T(n/2) + 1 → case 2, Θ(log n)
    # Karatsuba: T(n) = 3T(n/2) + n → case 1, Θ(n^1.58)
    # Strassen: T(n) = 7T(n/2) + n^2 → case 1, Θ(n^2.81)

    # Double n from 1024 to 2048 and see how much the total work grows:
    # merge sort about 2.2× (n log n grows slightly more than 2× when n doubles), Strassen about 7× (n^2.81)
    for a, b, d in [(2, 2, 1), (7, 2, 2)]:
        r = recursion_tree(a, b, d, 2048) / recursion_tree(a, b, d, 1024)
        print(f"a={a} b={b} d={d}: n doubles, work ×{r:.2f}")   # ×2.18, ×7.01

06Practice

• LeetCode 704Binary Search (T(n) = T(n/2) + 1)Easy
• LeetCode 912Sort an Array (write merge sort, then derive T(n) = 2T(n/2) + n)Medium
• LeetCode 50Pow(x, n) (T(n) = T(n/2) + 1)Medium
• LeetCode 241Different Ways to Add Parentheses (uneven subproblems, so the theorem does not apply)Medium
• LeetCode 932Beautiful Array (T(n) = 2T(n/2) + n)Medium
• LeetCode 218The Skyline Problem (the divide and conquer version is T(n) = 2T(n/2) + n)Hard