the master theorem

Solving divide-and-conquer recurrences by hand every time is tedious, and the same three patterns keep appearing. The Master Theorem is a lookup table that turns the recurrence T(n) = a T(n/b) + f(n) straight into an answer, as long as your recurrence has that exact shape. It is the single most-used shortcut in algorithm analysis.

It works by comparing two quantities. The recursive part wants to grow the work to n^(log_b a) (the cost if all the work lived at the leaves, where log_b a is the critical exponent). The combine part contributes f(n) per level. The theorem compares f(n) against n^(log_b a): Case 1 — f(n) is polynomially smaller, so the leaves dominate and T(n) = Theta(n^(log_b a)). Case 2 — they are the same size (f(n) = Theta(n^(log_b a))), every level costs about the same and a log factor appears, giving T(n) = Theta(n^(log_b a) log n). Case 3 — f(n) is polynomially larger and satisfies a regularity condition, so the root dominates and T(n) = Theta(f(n)). For T(n) = 2 T(n/2) + n: log_2 2 = 1, n^1 = n equals f(n) = n, so Case 2 gives Theta(n log n).

Used carefully it is almost magical, but be honest about its limits. It only applies to the equal-split form a T(n/b) + f(n); uneven splits need the Akra-Bazzi method. It requires a >= 1 and b > 1, and f(n) must be reasonably well-behaved. Crucially, there are GAPS: between Case 1 and Case 2, and between Case 2 and Case 3, the comparison must be by a polynomial factor (a factor of n^epsilon for some epsilon > 0), so a recurrence like T(n) = 2 T(n/2) + n / log n falls in a gap and the basic theorem says nothing — you need the tree method or an extended version.