The Master Theorem

The master theorem gives the running time of many divide-and-conquer recurrences by comparing the recursion's work to its combine step.

Solving recurrences by pattern

Many divide-and-conquer algorithms have a running time of the form T(n) = a T(n/b) + f(n), where the problem splits into a subproblems each of size n/b, and f(n) is the cost of dividing and combining. The master theorem reads off the closed-form solution by comparing f(n) against n raised to the power log-base-b of a, written n^c where c = log_b(a).

The three cases

• Case 1: if f(n) grows slower than n^c, the leaves dominate and T(n) = Theta(n^c)
• Case 2: if f(n) grows like n^c, work is even across levels and T(n) = Theta(n^c log n)
• Case 3: if f(n) grows faster than n^c (and is regular), the root dominates and T(n) = Theta(f(n))

Worked examples

Merge sort has a=2, b=2, so c=1, and f(n)=n matches n^1, which is case 2, giving Theta(n log n). Binary search has a=1, b=2, so c=0, and f(n) is constant, matching n^0, again case 2, giving Theta(log n). Naive matrix multiplication by blocks has a=8, b=2, so c=3, with f(n)=n^2 below n^3, which is case 1 giving Theta(n^3).

Its limits

The master theorem covers only recurrences of this specific shape with a constant number of equal-size subproblems. Recurrences where subproblem sizes differ, such as T(n)=T(n/3)+T(2n/3)+n, or where f(n) sits in a gap between the cases, need other tools like the recursion-tree method, the Akra-Bazzi theorem, or direct substitution.

Why it matters

The theorem turns the design of a divide-and-conquer algorithm into a quick calculation: choose how many subproblems and how much combining work, and the theorem predicts the asymptotic cost immediately, guiding whether a proposed split is worthwhile.