The master theorem in practice

BIGO-6 gave the master theorem for recurrences of the form T(n) = a T(n/b) + nᵈ. Real methods do not always fit that form: the work outside the calls may have a log in it, or the two parts may have different sizes. This lesson shows how to get the recurrence from code, how to handle those two cases, and how to check an answer by measuring.

From code to recurrence

To write the recurrence of a recursive function, read three things off the code:

• How many recursive calls one call makes. That is a.
• How big each call’s input is, compared with the original. Halves give n/2, so b = 2.
• How much work one call does outside its recursive calls: splitting, joining, copying. Call it f(n).

Then T(n) = a T(n/b) + f(n). Watch for hidden work. A slice such as a[:mid] copies mid values, so it costs O(n), not O(1) (BIGO-8). A call that sorts its part costs O(n log n). A loop over the part costs O(n).

def find(a, x, lo, hi):          # 1 call on half: T(n) = T(n/2) + 1
    ...

def total(a):                     # 2 calls on halves, plus 2 slices:
    if len(a) == 1:               # T(n) = 2 T(n/2) + n
        return a[0]
    mid = len(a) // 2
    return total(a[:mid]) + total(a[mid:])

def strip_sorted(points):         # 2 calls, plus a sort of the part:
    ...                           # T(n) = 2 T(n/2) + n log n

Floors and ceilings do not matter. A list of 7 values splits into 3 and 4, not two halves of 3.5. Writing T(⌊n/2⌋) + T(⌈n/2⌉) (⌊ ⌋ means round down, ⌈ ⌉ means round up) gives the same Θ answer as 2 T(n/2). The same is true of the base case: any fixed size and any fixed cost give the same answer.

Work with a log factor

Suppose each call sorts its part before combining, so T(n) = 2 T(n/2) + n log n. Here a = 2 and b = 2, but f(n) = n log n is not a power of n, so the basic theorem does not apply. Add up the levels instead. Level k has 2ᵏ parts of size n/2ᵏ, each doing about (n/2ᵏ) log₂(n/2ᵏ) work, so the level does n (log₂ n − k). Step through the third variant of the figure.

The levels shrink only slowly, so they do not form a series where the top term wins. Their sum is n × (log₂ n + (log₂ n − 1) + … + 1), about n (log₂ n)² / 2. So T(n) = Θ(n log² n), where log² n means (log n)²: log n multiplied by log n.

This is the case where every level costs about the same. When a is less than bᵈ the top level still wins, so the total is Θ of the top level’s work, log factor included. When a is greater than bᵈ the bottom level still wins, and the total is Θ(n to the power log_b a). Here log_b a, the logarithm of a in base b, is the power that b must be raised to to give a.

Lesson 4 meets this case. The closest-pair method sorts the points near the dividing line by y. Sorting them again in every call gives n log² n; passing the points up already sorted, as merge sort does, brings the work outside the calls down to O(n) and the total to n log n.

Parts of different sizes

Lesson 6 has a recurrence with two different calls: T(n) = T(n/5) + T(7n/10) + O(n). The master theorem needs equal parts. Draw the recursion tree and add up the levels. Step through the first two variants of the figure.

The figure shows the general rule. Add up the fractions of n that the calls receive.

• They add up to less than 1, as with 1/5 + 7/10 = 9/10. Each level does 9/10 of the work of the level above, so the levels form a shrinking series (BIGO-6) and the top level wins: T(n) = O(n). The constant is 1 / (1 − 9/10) = 10.
• They add up to exactly 1, as with 1/3 + 2/3. Every full level does n work, and the number of levels is a fixed multiple of log n: T(n) = Θ(n log n). The same holds for any fixed split, such as 1/10 and 9/10. This is why quicksort is O(n log n) whenever every pivot leaves at least a fixed fraction on each side.
• They add up to more than 1, as with T(n) = 2 T(n/2) + T(n/4) + n: 1/2 + 1/2 + 1/4 = 5/4. The levels grow, and the leaves win.

Worked examples

• Skyline (practice problem 2): split the buildings in half, find the outline of each half, then merge the two outlines in one pass from left to right, much like merging two sorted lists. T(n) = 2 T(n/2) + O(n), so O(n log n).
• Strassen’s matrix multiplication: multiplying two n × n matrices directly takes about n³ steps. Strassen (1969) splits each matrix into four blocks and needs 7 block products instead of 8, plus additions that cost O(n²). T(n) = 7 T(n/2) + n²: 7 > 2² = 4, so the leaves win, and the cost is n to the power log₂ 7, about n²·⁸¹. Lesson 5 uses the same idea on numbers.
• Quickselect with the worst pivots: each round drops only the pivot, so T(n) = T(n − 1) + n. The size shrinks by subtraction, not division, so unroll it: n + (n − 1) + … + 1 = n(n + 1)/2, which is O(n²).
• Closest pair with a strip sorted in every call: 2 T(n/2) + n log n, so Θ(n log² n). Sorted once: 2 T(n/2) + n, so Θ(n log n).
• Median of medians: T(n/5) + T(7n/10) + n, so O(n).

Checking by measuring

A cost can be checked by counting. Add a counter for the main operation, run the method on inputs of size n and 2n, and compare. Doubling n doubles an O(n) count, multiplies an O(n²) count by 4, and an O(n log n) count by a little more than 2. A count that grows as n to the power c multiplies by 2 to the power c.

import math

def count_calls(n, a, b):
    """How many calls a recursion makes: a calls, each on n // b."""
    if n <= 1:
        return 1
    return 1 + a * count_calls(n // b, a, b)

for n in (1024, 2048, 4096):
    c = count_calls(n, 3, 2)
    print(n, c, round(math.log2(c / count_calls(n // 2, 3, 2)), 3))
# 1024 88573 1.585 ... each doubling multiplies the count by 3:
# 2 to the power 1.585, as log2(3) = 1.585 predicts

Count operations rather than seconds when you can. Timings jump about with other programs, caches and Python’s memory manager, while a count is exact. The practice tests for problems 1 and 6 count comparisons for this reason.