Master theorem
- Algorithms course
- Intermediate
- Lesson 67/80
- 4 min
Solve T(n) = aT(n/b) + f(n).
Master theorem
The master theorem solves recurrences of the form T(n) = aT(n/b) + f(n). Here a is the subproblem count, b the split ratio.
It gives three cases; each yields a different complexity class and a quick solution.
The master theorem lets us quickly compute the complexity of divide and conquer algorithms.
Three cases
Case 1: if f(n) is small, T(n) = Θ(n^log_b a). Case 2: if f(n) = Θ(n^log_b a), then T(n) = Θ(n^log_b a * log n). Case 3: if f(n) is large, T(n) = Θ(f(n)).
Example: T(n) = 2T(n/2) + n, log_2 2 = 1, case 2, T(n) = Θ(n log n).
These cases quickly yield the Θ(n log n) result for algorithms like merge sort.
Practice Compute master
Write master_log_b_a(a, b). Return log_b a. Print 1.0 with print(master_log_b_a(2, 2)).
Starter code
def master_log_b_a(a, b):
# Compute log_b aSample solution
def master_log_b_a(a, b):
# Compute log_b a
import math
return math.log(a, b)
print(master_log_b_a(2, 2))Expected output
1.0
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Master theorem: match the terms
| Term | Meaning |
|---|---|
a |
Subproblem count |
b |
Split ratio |
f(n) |
Combine |
Θ |
Complexity |
2 What solves T(n) = 2T(n/2) + n?
- Θ(n^2)
- Θ(2^n)
- Θ(log n)
- Θ(n log n) Correct answer
Explanation: Θ(n log n).
3 Master formula
T(n) = aT(n/____) + f(n)T(n) = aT(n/b) + f(n)Explanation: b is right.