The Master Theorem's Three Cases

The master theorem solves a recurrence of the form T(n) = a·T(n/b) + f(n), with a at least 1 and b greater than 1, by comparing two quantities: f(n), the work at the root of the recursion tree, and n^(log_b a), the number of leaves. Whichever grows faster sets the answer, and when they grow at the same rate every level of the tree costs about the same, so the answer gains a factor of log n. This card covers the three cases, how to work out n^(log_b a), and the recurrences the theorem does not cover.

The leaf count comes from the tree. Each level has a times as many nodes as the one above, and there are log_b n levels below the root, so the bottom level has a^(log_b n) nodes, which equals n^(log_b a). Here log_b a is the power b has to be raised to in order to give a: log₂ 2 is 1, log₂ 4 is 2, and log₂ 1 is 0, since 2⁰ is 1.

"By a power of n" rules out a gap of only a logarithm: n log n grows faster than n, but not by a factor of n raised to any positive power, so it falls between the cases. The extra condition in case 3 holds for every polynomial f(n), such as n or n², so in practice it is only worth checking for unusual ones.

The theorem's answers are tight: the running time grows at exactly that rate, not merely at most at it. Textbooks write a tight bound with Θ, the Greek letter theta; this subject keeps to O, as everywhere else. Applied to the recurrences from this topic, and one with heavy work at the root, the theorem gives these results.

Binary search and merge sort are both case 2, with different leaf counts: binary search's tree is a single path, so its one leaf matches its constant work and the answer is the log n levels. The largest by halves does constant work over n leaves, so the leaves win and the cost is O(n), which is the n − 1 comparisons a loop makes. In the last row a quadratic combine outweighs everything below it, and the recursion adds nothing to the order.

Three recurrences do not fit. T(n) = T(n − 1) + O(n), a recursive insertion sort, subtracts from n instead of dividing it, and summing n + (n − 1) + … + 1 gives O(n²). T(n) = T(n/3) + T(2n/3) + O(n) splits into parts of unequal size; its recursion tree costs at most n on every level and has O(log n) levels, so it is O(n log n). T(n) = 2T(n/2) + O(n log n) has the logarithmic gap described above; extended versions of the theorem give O(n log² n).

The theorem turns most divide-and-conquer recurrences into a calculation with three numbers. The step that goes wrong is the comparison: it is n^(log_b a) against f(n), and a is in the exponent, so the number of calls changes the answer as much as the size of each.