Recipe
Apply the master theorem
Use when: you have a, b, and f(n)=\Theta(n^d) for a divide-and-conquer recurrence, and need its growth rate without building a recursion tree
Goal: the correct \Theta bound on T(n), by comparing the work exponent d to the critical exponent \log_b a
Taught in The master theorem · extends Read off a, b, f(n), and evaluate at a size
Quick recipe
-
1
Identify a and b the same way as always, then read the exponent d directly from f(n)=\Theta(n^d).
Example
T(n)=4T(n/2)+n^3: a=4, b=2, d=3.
Why: every later step is built entirely from these three numbers.
-
2
Take the logarithm of a base b.
Example
\log_2 4 = 2.
Why: this single number is what the work exponent d gets compared against; it summarizes how many leaves the recursion tree ultimately has.
-
3
Check whether the work exponent d from Step 1 is smaller than, equal to, or bigger than the critical exponent from Step 2.
Example
d=3 > \log_2 4=2, so the root dominates: T(n)=\Theta(n^3).
- d < \log_b a — the leaves dominate: T(n)=\Theta(n^{\log_b a}).
- d = \log_b a — every level costs the same: T(n)=\Theta(n^d\log n).
- d > \log_b a — the root already dominates: T(n)=\Theta(n^d).
Why: comparing exponents is exactly comparing the geometric level-sum ratio a/b^d to 1, which decides whether the leaf count or the per-level work wins asymptotically.
Common mistakes
- Comparing a to b^d numerically without ever taking the logarithm, which makes it easy to flip which side is bigger.
- Treating the balanced case's extra \log n factor as an unrelated growth rate instead of the same base rate multiplied by \log n.
- Applying this basic version of the theorem when f(n) isn't genuinely \Theta(n^d), such as when it involves a logarithm itself; that case needs the theorem's extended form.
- Applying the theorem to a recurrence that isn't of the exact aT(n/b)+f(n) shape, such as a subtractive recurrence like T(n-1)+n; the master theorem simply doesn't apply there.