Master's Theorem
Analyze divide-and-conquer algorithm complexity using the Master Theorem.
Solve T(n) = aT(n/b) + f(n) with worked examples.
The Formula
The Master Theorem provides a quick way to determine the time complexity of divide-and-conquer algorithms. Instead of solving complex recurrence relations by hand, you simply compare three values to get the answer.
Most fundamental algorithms — merge sort, binary search, Strassen's matrix multiplication — follow this pattern. The algorithm divides the problem into smaller subproblems, solves them recursively, then combines the results.
The theorem was introduced by Jon Bentley, Dorothea Haken, and James Saxe in 1980. It eliminates the need for detailed recurrence tree analysis in most practical cases.
Variables
| Symbol | Meaning | Unit |
|---|---|---|
| T(n) | Time complexity for input size n | — |
| a | Number of subproblems (a ≥ 1) | — |
| b | Factor by which input size is divided (b > 1) | — |
| d | Exponent of the work done outside recursion | — |
The Three Cases
Compare d with log_b(a):
| Case | Condition | Result |
|---|---|---|
| Case 1 | d < log_b(a) | T(n) = O(n^(log_b(a))) |
| Case 2 | d = log_b(a) | T(n) = O(n^d × log n) |
| Case 3 | d > log_b(a) | T(n) = O(n^d) |
Example 1
Merge Sort: T(n) = 2T(n/2) + O(n). What is the time complexity?
Identify: a = 2, b = 2, d = 1
Calculate log_b(a) = log₂(2) = 1
Compare: d = 1 = log_b(a) = 1 → Case 2
T(n) = O(n log n) — the well-known merge sort complexity
Example 2
Binary Search: T(n) = T(n/2) + O(1). What is the time complexity?
Identify: a = 1, b = 2, d = 0
Calculate log_b(a) = log₂(1) = 0
Compare: d = 0 = log_b(a) = 0 → Case 2
T(n) = O(n⁰ × log n) = O(log n)
Example 3
Strassen's Matrix Multiplication: T(n) = 7T(n/2) + O(n²). What is the complexity?
Identify: a = 7, b = 2, d = 2
Calculate log_b(a) = log₂(7) ≈ 2.807
Compare: d = 2 < 2.807 = log_b(a) → Case 1
T(n) = O(n^(log₂7)) ≈ O(n^2.807) — faster than the naive O(n³)
When to Use It
- Analyzing any divide-and-conquer algorithm's time complexity
- Quickly determining Big O without solving recurrence trees
- Comparing algorithm efficiency during design phase
- Technical interviews involving algorithm analysis
- Understanding why merge sort is O(n log n) and binary search is O(log n)