Which master-theorem case fits T(n)=2T(n/2)+O(n^2), and which fits T(n)=4T(n/2)+O(n)?
answer
- Find the watershed before anything else
- n raised to log base b of a
- Compare that quantity against f(n)
- A polynomially bigger f means the root wins
- A bigger watershed means the leaves win
basics
~20 sThe first is case 3: watershed n^(log_2 2) = n loses to f(n) = n^2, so the root dominates. The second is case 1: watershed n^(log_2 4) = n^2 beats f(n) = n, so the leaves do. Both give Θ(n^2).
solid answer
~40 sThe decision procedure is always the same: compute the watershed `n^(log_b a)`, then compare it with `f(n)`. For `2T(n/2)+O(n^2)`, log₂2 = 1 so the watershed is n, and n^2 is polynomially larger — case 3, answer Θ(f(n)) = Θ(n^2), with the work concentrated in the top call's combine step. For `4T(n/2)+O(n)`, log₂4 = 2 so the watershed is n^2, and the linear f(n) is polynomially smaller — case 1, answer Θ(n^(log_b a)) = Θ(n^2), with the work concentrated in the roughly n^2 leaves. Both land on Θ(n^2), and the case still matters: in the first, halving the combine step halves the total; in the second, the combine is free and only cutting the branching factor or splitting more aggressively moves the exponent.
go deeper
Know that the master theorem compares two things: the leaf total n^(log_b a) and the per-call work f(n). Being able to compute log base 2 of 4 as 2 and say which side is bigger is the expected depth here.
Run the comparison out loud on an unfamiliar recurrence rather than reciting case labels, name which end of the recursion dominates, and cite the polynomial-gap requirement that separates case 3 from a near miss.
Turn the case into an action: say whether optimising the combine step can possibly help, and recognise when a recurrence falls in a gap between the cases instead of forcing it into one.
Own the direction the analysis points a team: in a leaf-dominated design only the branching factor and split size move the exponent, so an effort to micro-optimise the combine loop is one you should redirect before it is funded.
## Stop memorising labels, run the comparison Candidates who learn the master theorem as "case 1, case 2, case 3" freeze when a recurrence does not look like a textbook one. The theorem is one comparison with three outcomes, and the comparison is between two specific quantities: - **The watershed, `n^(log_b a)`** — the total cost of the leaves of the recursion. There are roughly `a^(log_b n) = n^(log_b a)` base-case calls. - **`f(n)`** — the non-recursive work in one call, which is the work at the root of the recursion. Whichever grows faster dominates the total; if they grow at the same rate, every level costs the same and you pay for all log_b n of them. | comparison | case | result | where the work lives | |---|---|---|---| | f(n) = O(n^(log_b a − ε)) for some ε > 0 | 1 | Θ(n^(log_b a)) | the leaves | | f(n) = Θ(n^(log_b a)) | 2 | Θ(n^(log_b a) · log n) | evenly across levels | | f(n) = Ω(n^(log_b a + ε)), and a·f(n/b) ≤ c·f(n) for some c < 1 | 3 | Θ(f(n)) | the root | The ε in cases 1 and 3 is not decoration. It demands that the two sides differ by a **polynomial** factor, not merely by a logarithm — that is exactly where the theorem has gaps. ## Working the first recurrence: root-heavy `T(n) = 2T(n/2) + O(n^2)` gives a = 2, b = 2, so the watershed is `n^(log_2 2) = n^1 = n`. Is f(n) = n^2 polynomially larger than n? Yes, with ε = 1: n^2 = Ω(n^(1+1)). Case 3 also asks for the regularity condition, `a·f(n/b) ≤ c·f(n)` for some constant c < 1. Substituting: `2·(n/2)^2 = n^2/2 ≤ (1/2)·n^2`, so c = 1/2 works. Case 3 applies and the answer is **Θ(n^2)** — the same as the top-level combine alone. The shape of the cost is a geometric series that *shrinks* going down: n^2 at the root, n^2/2 at the next level, n^2/4 below that. The sum is at most 2n^2. The recursion is nearly free; the algorithm is its combine step. ## Working the second recurrence: leaf-heavy `T(n) = 4T(n/2) + O(n)` gives a = 4, b = 2, so the watershed is `n^(log_2 4) = n^2`. Is f(n) = n polynomially smaller than n^2? Yes, with ε = 1. Case 1 applies and the answer is **Θ(n^2)** — this time nothing to do with f(n), which never appears in the result. Here the series *grows* going down: n at the root, 4·(n/2) = 2n at the next level, 4n below that, doubling each level until the bottom, where roughly n^2 base cases sit. The last level dwarfs everything above it. ## Why the coincidence is the teaching point Two recurrences, one answer, two completely different algorithms. Knowing only "it's quadratic" tells you nothing about what to do next; knowing the case tells you exactly where to push: - **Root-heavy (case 3):** the total is Θ(f(n)). Any constant-factor improvement to the split-or-combine step is a constant-factor improvement to the whole algorithm, and an asymptotic improvement to f(n) can move the answer to a different class entirely — down to the watershed n, or into the balanced case. - **Leaf-heavy (case 1):** the total is Θ(n^(log_b a)) and f(n) is invisible. Optimising the combine step buys you nothing asymptotically. The only lever is the pair (a, b): fewer subproblems or smaller ones. This is why the classical fast big-number and matrix algorithms all work by *eliminating a subproblem* rather than by speeding up the arithmetic around it. - **Balanced (case 2):** every level matters equally; the log factor is the count of levels, and both f(n) and the branching are worth attention. ## The gaps, stated honestly The theorem does not cover every recurrence of the right form. If f(n) is larger than the watershed but only by a logarithmic factor — say `T(n) = 2T(n/2) + n·log n`, where the watershed is n — then f(n) is not Ω(n^(1+ε)) for any positive ε, so case 3 does not apply, and it is not Θ(n) either, so case 2 does not apply. The true answer, Θ(n·log²n), needs an extended form of the theorem or a direct summation. Likewise, case 3 can fail its regularity condition for oscillating or pathological f, though every polynomial f you are likely to meet satisfies it. When you hit a gap, say so out loud. "The three standard cases do not cover this because f exceeds the watershed by only a log factor" is a strong answer; forcing the recurrence into case 3 anyway is a wrong one.
- What if f(n) is larger than the watershed but not polynomially larger?Then no standard case applies. For T(n) = 2T(n/2) + n·log n the watershed is n and f exceeds it by only a log factor, so there is no ε making case 3's condition hold; the true answer is Θ(n·log²n). Recognising the gap and naming a direct summation or an extended form of the theorem as the way out is the expected answer.
- Why does case 3 carry a regularity condition on top of the size comparison?Because the case claims the root's work dominates a geometric sum, which needs the per-level cost to actually shrink. The condition a·f(n/b) ≤ c·f(n) for some c < 1 guarantees exactly that. Every ordinary polynomial f satisfies it, so it rarely bites in practice, but citing it shows you know the case is a theorem and not a rule of thumb.
- In a leaf-heavy recurrence, what actually moves the exponent?Only a and b. The exponent is log_b a, so you either spawn fewer subproblems or make each one smaller. Speeding up the split-and-combine work changes nothing asymptotically, because f(n) does not appear in the case-1 result at all — a fact worth checking before anyone spends a sprint optimising the wrong loop.
saying these in an interview costs you the question
- Compares f(n) against n instead of against n^(log_b a)
- Assumes a larger f(n) always makes the total larger
- Puts any f above the watershed into case 3 without the polynomial gap
- Reads log_b a as a divided by b
- Treats identical answers as meaning identical cost structure