Divide & Conquer Recurrence Relations
Use Master Theorem for T(n)=aT(n/b)+f(n).
complexityrecurrencemaster-theoremUpdated 2025-09-01
Cases
- Compare f(n) to n^{log_b a}
Example
- Merge sort: a=2,b=2,f(n)=n → O(n log n)
Use Master Theorem for T(n)=aT(n/b)+f(n).