Questions
21 of 29
What is the Master Theorem? When can it be applied?
Master Theorem for Divide-and-Conquer Recurrences
- 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
Difficulty: 8/10
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?