When you unroll T(n)=2T(n/2)+cn by substitution, what stops the expansion and sets the log factor?

## The method Unrolling (also called iteration, or the expansion half of the substitution method) solves a recurrence by repeatedly replacing `T` of a smaller argument with the recurrence's own right-hand side, until a pattern appears that you can close in terms of a round counter k. It is the algebraic twin of the recursion tree: the tree sums the work by *levels*, unrolling accumulates it by *rounds*, and they must agree. Running both is a cheap and effective check on an answer you are about to state out loud. ## Unrolling the canonical divide-and-merge recurrence Start from `T(n) = 2T(n/2) + cn`, where cn stands for the linear pass a call performs itself. Round 1 — replace `T(n/2)` with `2T(n/4) + c(n/2)`: > T(n) = 2·[2T(n/4) + c·n/2] + cn = 4T(n/4) + cn + cn = 4T(n/4) + 2cn Round 2 — replace `T(n/4)` the same way: > T(n) = 8T(n/8) + 3cn The structure is already visible. After **k** rounds: > T(n) = 2^k · T(n/2^k) + k·cn Read the two terms separately, because they mean different things: - **k·cn** is the work already accounted for — one full cn per round. This is the tree's statement that every level costs about n, seen from a different angle. - **2^k·T(n/2^k)** is the debt not yet expanded: 2^k pending subproblems, each of size n/2^k. ## What stops it The expansion is not stopped by the algebra; it is stopped by the **base case**. Recursion has to bottom out somewhere — at size 1, or at a fixed small cutoff — and the moment the argument n/2^k reaches that size, the leftover `T` is a known constant rather than something to expand further. With a base case at size 1: > n/2^k = 1 ⇒ 2^k = n ⇒ **k = log₂ n** Substituting that k back: > T(n) = 2^(log₂ n) · T(1) + (log₂ n)·cn = n·T(1) + cn·log₂ n The first term is Θ(n) — there are n base-case calls, each costing a constant, and base cases are not free. The second is Θ(n log n) and dominates. So **T(n) = Θ(n log n)**. This is the answer to "where does the log come from": it is the number of rounds, and the number of rounds is fixed by how many times you can divide n by the branching's shrink factor before hitting the base case. The log factor is a property of the *stopping point*, not something that materialises out of the notation. ## Four things that go wrong **Unrolling forever.** Without a stopping condition there is no answer, only an infinite regress. Candidates who cannot say what stops the expansion usually cannot say where the log came from either — the two questions have the same answer. **Treating the leftover term as zero.** `2^k·T(n/2^k)` is Θ(n) here, not nothing. In this recurrence it is dominated, but in `T(n)=2T(n/2)+O(1)` the same term is the *entire* answer: k·c·1 gives only Θ(log n) of accumulated work, while the leftover n·T(1) is Θ(n). Dropping it there produces a badly wrong bound. **Mis-accumulating the work term.** The common slip is writing `2^k·cn` instead of `k·cn`, reasoning that the number of calls doubles so the work must double. It does double in *count*, but each call's input has halved, so each round contributes exactly one more cn. Writing out three rounds explicitly, rather than jumping to a guessed pattern, catches this. **Calling the unrolled result a proof.** Expansion gives a *candidate* closed form, obtained by assuming the pattern continues and, usually, that n is an exact power of two so the divisions come out whole. The rigorous version guesses that closed form and verifies it by induction, and a full treatment also shows the floors and ceilings on n/2 do not change the class. In an interview it is enough to state that you would confirm by induction and that rounding does not affect the bound — but stating it is what separates "I know the ritual" from "I know why the ritual is valid". ## Base cases larger than one Real implementations rarely recurse down to a single element; they stop at a cutoff — say 32 — and finish with a simple method that has better constants at that size. The unrolling adapts directly: the stop condition becomes n/2^k = 32, so k = log₂ n − 5. Five fewer rounds means five fewer cn terms, and the number of leftover subproblems drops to n/32. The class is unchanged at Θ(n log n); the constant improves, sometimes substantially. That is exactly the shape of the argument for cutoffs: an asymptotically irrelevant, practically real win, and being able to show it in the recurrence keeps the discussion honest. ## Cross-checking against the tree The tree says: log₂ n levels, each costing cn, plus n leaves at Θ(1). Unrolling says: log₂ n rounds each contributing cn, plus a leftover of n·T(1). Same two terms, derived two ways. When the two disagree, the mistake is almost always in the accumulated work term of the unrolling — and finding that disagreement before you say the answer out loud is the whole point of knowing both methods.