Master Theorem
The master theorem gives the asymptotic bound of the divide-and-conquer recurrence T(n)=aT(n/b)+f(n) in three cases comparing f with n^(log_b a).
Purpose
To analyze divide-and-conquer complexity quickly without expanding the recursion.
Mechanism
Let c=log_b a. Case 1: f=O(n^(c-ε)) → T=Θ(n^c). Case 2: f=Θ(n^c log^k n) → T=Θ(n^c log^(k+1) n). Case 3: f=Ω(n^(c+ε)) plus the regularity condition → T=Θ(f).
Use cases
- Complexity analysis
- Divide-and-conquer algorithms
- Recurrence solving