The Master Theorem
The master theorem gives a quick closed-form solution for the running time of many divide-and-conquer recurrences.
The recurrence form
The master theorem solves recurrences of the form T(n) = a T(n/b) + f(n), where a is the number of subproblems, n/b is their size, and f(n) is the work to split and combine. Many divide-and-conquer algorithms fit this shape exactly.
The three cases
Compare f(n) to n^(log_b a), the cost of the leaves of the recursion tree. The theorem's answer depends on which dominates.
- Case 1: f(n) grows slower than n^(log_b a); result is Theta(n^(log_b a))
- Case 2: f(n) matches n^(log_b a); result is Theta(n^(log_b a) log n)
- Case 3: f(n) grows faster (and satisfies a regularity condition); result is Theta(f(n))
Worked applications
Merge sort: T(n) = 2 T(n/2) + O(n). Here log_b a = log_2 2 = 1, and f(n) = n matches n^1, so Case 2 gives Theta(n log n). Binary search: T(n) = T(n/2) + O(1), where log_b a = 0 and f(n) = 1 matches, giving Theta(log n).
When it does not apply
The master theorem covers only recurrences of its specific form with a constant number of equally sized subproblems. It does not handle unequal splits, subtractive recurrences like T(n) = T(n-1) + f(n), or non-polynomial gaps between the cases. Those need the recursion-tree or substitution method.
Why it is handy
For the large family of algorithms it covers, the master theorem replaces a full derivation with a one-line comparison. It lets you read off the complexity of a divide-and-conquer design almost by inspection, which is why it is a staple of algorithm analysis.
The intuition
The three cases correspond to where the work concentrates: at the leaves (Case 1), spread evenly across levels (Case 2), or at the root (Case 3). Understanding that the answer is simply the dominant term of the recursion tree makes the theorem easy to remember and apply.