The Master Theorem

A shortcut for divide and conquer

Many divide-and-conquer algorithms have recurrences of the form T(n) = a·T(n/b) + f(n): the problem splits into a subproblems of size n/b, with f(n) work to divide and combine. The master theorem compares f(n) with the critical function n^(log_b a), the total work done at the leaves of the recursion tree. Case 1: if f(n) grows polynomially slower than n^(log_b a), the leaves dominate and T(n) = Θ(n^(log_b a)). Case 2: if f(n) = Θ(n^(log_b a) · logᵏ n) for some k ≥ 0 (most often k = 0, the same rate), every level does about the same work and T(n) = Θ(n^(log_b a) · logᵏ⁺¹ n). Case 3: if f(n) grows polynomially faster and satisfies a regularity condition (a·f(n/b) ≤ c·f(n) for some c < 1), the root dominates and T(n) = Θ(f(n)). The theorem does not apply to recurrences such as T(n) = T(n − 1) + n or to uneven splits, which need unrolling or the Akra–Bazzi method.

Master theorem examples

Compute log_b a, compare with f(n), pick the case.

recurrence                  a  b  n^(log_b a)    f(n)      case  result
--------------------------  -  -  -------------  --------  ----  --------------------
binary search: T(n/2)+1     1  2  n^0 = 1        1         2     Theta(log n)
merge sort: 2T(n/2)+n       2  2  n^1            n         2     Theta(n log n)
tree traversal: 2T(n/2)+1   2  2  n              1         1     Theta(n)
Karatsuba: 3T(n/2)+n        3  2  n^1.585        n         1     Theta(n^1.585)
Strassen: 7T(n/2)+n^2       7  2  n^2.807        n^2       1     Theta(n^2.807)
2T(n/2)+n^2                 2  2  n              n^2       3     Theta(n^2)

not applicable: T(n) = T(n-1) + n   (subtract, not divide) -> unroll: Theta(n^2)

Compute log_b a first

Most mistakes come from comparing f(n) with the wrong exponent. Write down a, b and log_b a explicitly, then compare f(n) with n^(log_b a) before choosing a case.

Quick check: Using the master theorem, what is T(n) = 4T(n/2) + n?

• Θ(n²)
• Θ(n)
• Θ(n log n)
• Θ(n² log n)