Master Theorem

Definition

The Master Theorem is a formula that directly determines the asymptotic time complexity of divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n), without requiring the recurrence to be expanded and solved manually.

Overview

Divide-and-conquer algorithms — mergesort, binary search, matrix multiplication via Strassen's algorithm — naturally produce recurrence relations describing their running time: solve a problems of size n/b, plus f(n) work to divide and combine results. Solving such a recurrence from scratch, by expanding it into a recursion tree and summing costs at each level, is tedious and error-prone to redo for every new algorithm. The Master Theorem packages that recursion-tree analysis into a reusable formula, letting anyone plug in a, b, and f(n) and read off the answer directly, provided the recurrence fits its standard form. The theorem works by comparing f(n), the cost of dividing and combining, against n^(log_b a), the cost implied purely by the branching and shrinking of the recursive calls. Three cases follow from that comparison. If f(n) grows polynomially slower than n^(log_b a), the recursive calls dominate and T(n) = Θ(n^(log_b a)) — this is the case for binary search, whose combine step is O(1). If f(n) grows at the same polynomial rate, both levels contribute equally and a logarithmic factor appears, giving T(n) = Θ(n^(log_b a) · log n) — this is the case for mergesort, where the merge step is linear and matches the branching cost. If f(n) grows polynomially faster than n^(log_b a), the top-level combine work dominates and T(n) = Θ(f(n)), subject to a regularity condition on f(n). The theorem has limits: it doesn't apply when a or b aren't constants, when the subproblems aren't equally sized, or when there's a polynomial gap between f(n) and n^(log_b a) that doesn't cleanly fall into one of the three cases — situations that require more general tools like the Akra-Bazzi method. Despite these gaps, the Master Theorem covers a large share of recurrences that show up in practice and is a standard part of algorithms coursework precisely because it turns a multi-step derivation into a quick, mechanical lookup.

Key Concepts

• Solves recurrences of the form T(n) = aT(n/b) + f(n) directly
• Compares f(n) against n^(log_b a) to determine which of three cases applies
• Case 1: recursive work dominates, giving Θ(n^(log_b a))
• Case 2: balanced work, giving Θ(n^(log_b a) · log n), as in mergesort
• Case 3: combine work dominates, giving Θ(f(n)), under a regularity condition
• Avoids manually expanding a recursion tree for every new recurrence
• Does not apply to unequal subproblem sizes or non-constant a/b
• Complemented by the more general Akra-Bazzi method for edge cases

Use Cases

Frequently Asked Questions

Related in Computer Science