masterteoremet

The Master Theorem is a standard tool in the analysis of divide-and-conquer algorithms. It provides asymptotic bounds for recurrences of the form T(n) = a T(n/b) + f(n), where a >= 1, b > 1, and n is large.

The key quantity is n^{log_b a}, often called the critical exponent. The relative growth of f(n) compared with n^{log_b a} determines the overall solution.

Case 1: If f(n) = O(n^{log_b a - epsilon}) for some epsilon > 0, then T(n) = Theta(n^{log_b a}).

Case 2: If f(n) = Theta(n^{log_b a} log^k n) for some k >= 0, then T(n) = Theta(n^{log_b a} log^{k+1} n).

Case 3: If f(n) = Omega(n^{log_b a + epsilon}) for some epsilon > 0, and the regularity condition a f(n/b) <= c f(n) holds for some c < 1 and large n, then T(n) = Theta(f(n)).

Examples help illustrate. Merge sort has a = 2, b = 2, f(n) = Theta(n), and log_b a = 1, so f(n) = Theta(n^{log_b a}). This places the recurrence in Case 2 and yields T(n) = Theta(n log n). Another example: T(n) = 7 T(n/2) + O(n^2) has log_b a ≈ 2.807 and f(n) = O(n^2), which is Case 1, giving T(n) = Theta(n^{log_2 7}).

Limitations: The theorem applies strictly to recurrences of the specified form with the stated regularity conditions. For more general splits or non-polynomial f(n), extensions such as the Akra-Bazzi theorem may be used.