Questions
23 of 29
What is the Master Theorem? When can it be applied?
Difficulty: 9/10
Master Theorem
The Master Theorem is a mathematical technique for determining the asymptotic complexity of certain divide-and-conquer recurrences. It applies to recurrences of the general form T(n) = aT(n/b) + f(n), where a represents the number of recursive subproblems, n/b represents the size of each subproblem, and f(n) represents the non-recursive work.
javascript
It is commonly applied to algorithms such as merge sort and many divide-and-conquer algorithms. It should not be applied blindly to recurrences that do not satisfy its required form.
Follow-up Questions
- What are the three main cases of the Master Theorem?
- Why does Merge Sort have O(n log n) complexity?
- When does the Master Theorem not apply?