What is the Master Theorem? When can it be applied?
Master Theorem for Divide-and-Conquer Recurrences
The Master Theorem is a formula used to determine the time complexity of divide-and-conquer algorithms whose running time can be expressed as a recurrence of the form T(n) = a*T(n/b) + f(n), where a is the number of subproblems, n/b is the size of each subproblem, and f(n) is the cost of the work done outside the recursive calls, such as combining results.
It compares f(n) against n^(log_b(a)) to determine which term dominates the recurrence, and provides the resulting asymptotic complexity in three cases without needing to manually unroll the recursion tree.
- 1
Case 1: If f(n) = O(n^(log_b(a) - ε)), then T(n) = Θ(n^log_b(a)) — work is dominated by leaves
- 2
Case 2: If f(n) = Θ(n^log_b(a)), then T(n) = Θ(n^log_b(a) * log n) — work is evenly distributed
- 3
Case 3: If f(n) = Ω(n^(log_b(a) + ε)) and regularity condition holds, then T(n) = Θ(f(n)) — work is dominated by the root
It applies only to recurrences of that specific form with constant a ≥ 1 and b > 1; it does not directly apply to recurrences with variable subproblem sizes, subtractive recurrences like T(n) = T(n-1) + f(n), or when a or b are not constants. In those cases, the Recursion Tree or Substitution Method is used instead.
Follow-up Questions
- Apply the Master Theorem to Merge Sort's recurrence T(n) = 2T(n/2) + O(n).
- What do you do when the Master Theorem doesn't apply?