master theorem

The master theorem is a cookbook for solving a very common shape of recurrence: T(n) = aT(n/b) + f(n). Here a is how many subproblems you make, b is the factor by which each subproblem is smaller, and f(n) is the extra work you do outside the recursive calls — the splitting and combining. Many divide-and-conquer algorithms produce exactly this form, and instead of solving each one from scratch, you can read off the answer by comparing two quantities.

The two quantities you compare are f(n) — the work done at one level — against n^(log_b a), which measures how fast the number of leaf-level subproblems grows. The theorem has three cases. Case 1: if the leaf work n^(log_b a) grows faster than f(n), the bottom of the recursion dominates and T(n) = O(n^(log_b a)). Case 2: if they grow at the same rate, every level costs about the same and you pay that cost across all log n levels, giving T(n) = O(n^(log_b a) · log n). Case 3: if f(n) grows faster, the top level dominates and T(n) = O(f(n)).

Merge sort is the textbook fit: T(n) = 2T(n/2) + O(n), so a = 2, b = 2, and n^(log_b a) = n^(log_2 2) = n. The combine work f(n) = O(n) grows at the same rate as n, which is case 2 — every level costs O(n), there are log n levels, and the total is O(n log n). One honest caveat: the master theorem only covers recurrences of this particular form with roughly equal-sized subproblems, and case 3 needs a mild 'regularity' condition. When a recurrence does not fit, fall back to a recursion tree or induction.