Recurrences & the Master Theorem

Recurrences

A recursive algorithm’s running time is naturally described by a recurrence: the time for size n in terms of the time for smaller sizes. A divide-and-conquer algorithm that splits a problem into a subproblems of size n/b and spends f(n) time dividing and combining has

T(n) = a · T(n / b) + f(n),        T(1) = constant

The recursion-tree method

Draw every call as a node. The root is the whole problem; its children are its a subproblems, and so on, until the leaves of size 1.

The total time is the sum of all the levels. The 3D model draws the tree and a bar for each level’s work:

There are only three possible patterns:

1. The work grows going down (Karatsuba, 4T(n/2) + n): the leaves dominate.
2. The work is the same on every level (merge sort, binary search): total = work per level × number of levels.
3. The work shrinks going down (2T(n/2) + n²): the root dominates, because a decreasing geometric series is at most a constant times its first term.

The master theorem

The master theorem turns these three patterns into a formula. Compare f(n) with n^c, where c = log_b a is the critical exponent (the number of leaves is n^c). For f(n) = Θ(n^k):

Worked examples

• Merge sort: a = 2, b = 2 → c = 1; f(n) = n, k = 1 = c → case 2 → Θ(n log n).
• Binary search: a = 1, b = 2 → c = 0; f(n) = 1 = n⁰ → case 2 → Θ(log n).
• Karatsuba: a = 3, b = 2 → c = log₂ 3 ≈ 1.585 > k = 1 → case 1 → Θ(n^1.585), which beats the Θ(n²) school method.
• Strassen: a = 7, b = 2 → c = log₂ 7 ≈ 2.807 > k = 2 → case 1 → Θ(n^2.807), which beats Θ(n³).
• T(n) = 2T(n/2) + n²: c = 1 < k = 2 → case 3 → Θ(n²).

The general form

For an arbitrary f(n), the conditions compare f(n) with n^c polynomially:

1. If f(n) = O(n^{c − ε}) for some ε > 0, then T(n) = Θ(n^c).
2. If f(n) = Θ(n^c log^p n) with p ≥ 0, then T(n) = Θ(n^c log^p+1 n).
3. If f(n) = Ω(n^{c + ε}) for some ε > 0, and a·f(n/b) ≤ k·f(n) for some k < 1 (the regularity condition), then T(n) = Θ(f(n)).

For example, T(n) = 2T(n/2) + n log n has c = 1 and f(n) = n log n = Θ(n¹ log¹ n), so the extended case 2 gives Θ(n log² n).

When it does not apply

• Subtract-and-conquer recurrences such as T(n) = T(n − 1) + n (insertion sort, the worst case of quick sort): unroll them instead, n + (n − 1) + … + 1 = Θ(n²).
• Unequal splits such as T(n) = T(n/3) + T(2n/3) + n: use a recursion tree (every level does at most n work over about log_3/2 n levels, so Θ(n log n)) or the Akra–Bazzi method.
• f(n) in the gaps, such as n / log n against n¹: neither polynomially smaller nor equal.

Code

import math

def level_work(a, b, k, n):
    """Work on each level of the recursion tree of T(n) = a T(n/b) + n^k, with T(1) = 1."""
    levels, size, count = [], n, 1
    while True:
        levels.append(count * size ** k)          # count subproblems, each costing size^k
        if size == 1:
            return levels
        size //= b
        count *= a

def T(a, b, k, n):
    """The recurrence itself, evaluated directly."""
    return 1 if n == 1 else a * T(a, b, k, n // b) + n ** k

def power(e):
    """n^e written the usual way."""
    if e == 0:
        return '1'
    if e == 1:
        return 'n'
    return f'n^{e:g}' if float(e).is_integer() else f'n^{e:.3f}'

def master(a, b, k):
    """Master theorem for f(n) = n^k: compare k with the critical exponent log_b(a)."""
    c = math.log(a, b)
    if math.isclose(k, c):
        return 'case 2: Theta(log n)' if k == 0 else f'case 2: Theta({power(k)} log n)'
    if k < c:
        return f'case 1: Theta({power(c)})'               # the leaves dominate
    return f'case 3: Theta({power(k)})'                   # the root dominates

EXAMPLES = [('merge sort', 2, 2, 1, 16), ('binary search', 1, 2, 0, 16), ('Karatsuba', 3, 2, 1, 8),
            ('2T(n/2) + n^2', 2, 2, 2, 16), ('4T(n/2) + n', 4, 2, 1, 8)]
for name, a, b, k, n in EXAMPLES:
    lv = level_work(a, b, k, n)
    assert sum(lv) == T(a, b, k, n)              # the tree adds up to the recurrence
    print(f'{name:14} levels {lv}  total {sum(lv)}  {master(a, b, k)}')
# merge sort     levels [16, 16, 16, 16, 16]  total 80  case 2: Theta(n log n)
# binary search  levels [1, 1, 1, 1, 1]  total 5  case 2: Theta(log n)
# Karatsuba      levels [8, 12, 18, 27]  total 65  case 1: Theta(n^1.585)
# 2T(n/2) + n^2  levels [256, 128, 64, 32, 16]  total 496  case 3: Theta(n^2)
# 4T(n/2) + n    levels [8, 16, 32, 64]  total 120  case 1: Theta(n^2)

Common mistakes

• Comparing f(n) with n instead of n^{log_b a}. The yardstick depends on a and b.
• Swapping a and b. a is the number of subproblems, b the factor by which the size shrinks. c = log_b a, not log_a b.
• Forgetting the log factor in case 2. Equal work on every level is multiplied by the number of levels, log n.
• Using the basic three cases when f(n) has a log factor. n log n is not polynomially larger than n; use the extended case 2.
• Applying it to T(n − 1) recurrences. The master theorem only covers subproblems of size n/b.