Master Theorem
Solve divide-and-conquer recurrences by comparing work to the watershed.
The idea
The master theorem gives the growth rate of the running time $T(n)$ of a divide-and-conquer algorithm, one that splits a size-$n$ instance into $a$ subproblems of size $n/b$ and spends $f(n)$ dividing and combining, by comparing $f(n)$ with the watershed function $n^{\log_b a}$.
Theorem (Master theorem).
Let $a \ge 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T(n)$ satisfy the recurrence $T(n) = a\,T(n/b) + f(n).$ Then: 1. If $f(n) = O(n^{\log_b a - \varepsilon})$ for some $\varepsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$. 2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$. 3. If $f(n) = \Omega(n^{\log_b a + \varepsilon})$ for some $\varepsilon > 0$, and $a\,f(n/b) \le c\,f(n)$ for some constant $c < 1$ and all large $n$, then $T(n) = \Theta(f(n))$.
The watershed is the total cost of the recursion tree's leaves: the tree has branching factor $a$ and depth $\log_b n$, so it ends in $a^{\log_b n} = n^{\log_b a}$ leaves. The three cases are the three ways work can be distributed over that tree. In Case 1 the per-level work grows geometrically toward the bottom, so the leaves dominate and set the answer. In Case 3 it shrinks geometrically going down, so the root call dominates and the answer is $f(n)$ itself. In Case 2 all $\log_b n$ levels cost the same, and the total is that common cost times the number of levels, which contributes the factor $\log n$.
The theorem does not settle every recurrence: when $f(n)$ exceeds the watershed by less than a polynomial factor, the recurrence falls between the cases and another method is needed.
Ways to work on it
- Walkthrough. Place a recurrence in one of three cases by comparing leaf and root costs, with merge sort as the example.
- Practice. Classify a recurrence into the right Master Theorem case.
- Hardest. Fully solve a recurrence, checking every condition the theorem asks for.
Not sure where to start? Take the ten-question placement test.