Both T(n)=T(n/2)+O(1) and T(n)=2T(n/2)+O(n) halve the input, so why isn't each O(log n)?
answer
- two dials, not one
- how many calls survive each split
- add up one whole level at a time
- nodes at level i times work each
- constant per level versus n per level
basics
~10 sHalving only sets the number of levels, about log n; the work per level decides the rest. T(n)=T(n/2)+O(1) does O(1) per level, so O(log n). T(n)=2T(n/2)+O(n) does O(n) per level, so O(n log n).
solid answer
~40 sA recurrence carries three separate facts: how many subproblems one call spawns, how much smaller each one is, and how much non-recursive work the call itself does. Halving the size only tells you the recursion is about log n levels deep — it says nothing about how wide the tree gets or what a level costs. In `T(n)=T(n/2)+O(1)` a single subproblem survives each step, so each level costs O(1) and the total is just the depth: O(log n). In `T(n)=2T(n/2)+O(n)` the subproblem count doubles exactly as fast as the sizes shrink, so every level re-does about n units of work, and log n levels of that is O(n log n). The sentence I would say out loud is: total cost equals work per level times number of levels, summed honestly when the levels differ.
go deeper
Recall that a recurrence has two dials: how many recursive calls a step makes, and how much work the step does itself. Be ready to state that T(n)=T(n/2)+O(1) is O(log n) while T(n)=2T(n/2)+O(n) is O(n log n).
Explain the level-by-level accounting out loud: at depth i there are 2^i calls on inputs of size n/2^i, so the per-level cost stays at about n. Show where the log factor comes from and why it counts levels, not total work.
Demonstrate that you check the per-call work before quoting a bound, including work hidden inside helpers that walk the input. Interviewers want the derivation applied to unfamiliar code, not a memorised answer for a familiar algorithm.
Own the framing that a recurrence is a cost model with assumptions baked in: even splits, uniform per-item cost, constants discarded. Be ready to say when that model is good enough for a capacity decision and when you would insist on measurement instead.
## What a recurrence actually says A recurrence relation `T(n)` is a cost model written in the algorithm's own shape: the time to solve an input of size n, expressed in terms of the time to solve strictly smaller inputs, plus whatever the call does on its own. Reading one means separating three independent facts: - **a** — how many recursive calls one invocation makes (the branching factor). - **n/b** — how big each of those subproblems is relative to the input. - **f(n)** — the *non-recursive* work: the loops, scans, merges, allocations and helper calls the invocation performs itself. `T(n) = 2T(n/2) + O(n)` reads: two calls, each on half the input, plus a linear pass. `T(n) = T(n/2) + O(1)` reads: one call on half the input, plus constant work. ## The picture that resolves the confusion Draw the recursion tree. One node per call; the node's label is that call's own `f(size)`, not its total cost; each node has **a** children of size **n/b**. The answer is the sum of every label in the tree, and the reliable way to add them up is level by level: > level cost = (number of nodes at that level) × (work each of those nodes does) **Case one, `T(n)=T(n/2)+O(1)`.** Level i has exactly one node, of size n/2^i, doing c work. Every level costs c. The sizes reach the base case after about log₂ n halvings, so the tree is a single chain of length log₂ n and the total is c·log₂ n = O(log n). The tree here is a stick, not a tree. **Case two, `T(n)=2T(n/2)+O(n)`.** Level i has 2^i nodes, each of size n/2^i, each doing c·n/2^i work. Multiply: 2^i · c·n/2^i = c·n. The node count grows at exactly the rate the per-node work shrinks, so **every level costs about n**. There are still about log₂ n levels, so the total is c·n·log₂ n = O(n log n). The bottom level holds 2^(log₂ n) = n leaves doing O(1) each, which is O(n) — one level's worth, so the leaves do not change the class. The misconception "it halves, so it's logarithmic" collapses depth into total. Depth is only one of the two factors. ## Turning the two dials independently The branching factor and the per-call work move separately, and all four combinations show up in real code: | Recurrence | Per-level work | Total | |---|---|---| | `T(n)=T(n/2)+O(1)` | constant, c | Θ(log n) | | `T(n)=T(n/2)+O(n)` | n, then n/2, n/4, … | Θ(n) | | `T(n)=2T(n/2)+O(1)` | 1, 2, 4, … up to n | Θ(n) | | `T(n)=2T(n/2)+O(n)` | n at every level | Θ(n log n) | Row two is worth staring at: one call on half the data but a linear scan first sums to n + n/2 + n/4 + … < 2n, a decreasing geometric series, so the whole thing is linear and the top call dominates. Row three is the mirror image: the work per node is constant but the node count doubles, so the n leaves dominate and the total is linear again. Only when the level costs are all equal does a log factor appear from the depth. ## Details that trip people up **The base of the logarithm is a constant factor.** log₄ n = log₂ n / 2. A tree of depth log₄ n and a tree of depth log₂ n are the same asymptotic class; the difference lives in the constant, which matters for wall-clock time and never for the O( ) label. **The base case both stops the tree and populates the bottom level.** Recursion that bottoms out at size 1 gives a tree of depth log n; one that bottoms out at a fixed cutoff of, say, 32 gives depth log n − 5 — the same class, a slightly better constant. **f(n) includes everything the call does that is not a recursive call.** A helper that walks the whole input before recursing is part of f(n) even though it looks like a single line. This is the single most common way a hand-written recurrence comes out wrong: the reader counts the recursive calls correctly and undercounts the work around them. **Uneven splits usually keep the class.** Splitting one-third/two-thirds with linear work still gives Θ(n log n) — the deepest path is longer (log base 3/2 instead of log base 2) but the per-level work is still bounded by n. What changes the class is changing how fast the total size shrinks per level, or changing f(n). ## What to say in the room State the recurrence first, out loud, from the code. Then say what one level costs and how many levels there are, and only then give the bound. That order makes the reasoning checkable, and it is what separates a candidate who derived the answer from one who memorised that merge-sort-shaped recurrences are n log n.
- What is the total for T(n)=2T(n/2)+O(1), where the split is binary but the per-call work is constant?Θ(n). Level i holds 2^i nodes each doing constant work, so the level costs grow 1, 2, 4, … up to about n at the bottom. That is an increasing geometric series dominated by its last term, and there are about n leaves, so the leaves alone account for the answer. No log factor appears because the levels are not equal — the bottom one swamps everything above it.
- And T(n)=T(n/2)+O(n) — one recursive call, but a linear scan before it?Θ(n), not Θ(n log n). The level costs are n, n/2, n/4, … which sum to less than 2n. It is a decreasing geometric series, so the root's own work dominates the entire recursion and the depth is irrelevant to the total. This is the recurrence people most often over-charge, because they see a linear pass and log n levels and multiply them.
- Does it matter whether you write O(n) or exactly cn for the per-call work?Not for the class, but be careful about what O( ) hides. Summing O( ) terms across a number of levels that itself depends on n is where sloppy notation produces wrong answers, so when the derivation gets delicate, carry a concrete cn and drop the constant at the end. It also keeps you honest about which term dominates when two terms are close.
Depth is how many floors the building has; per-level work is how much floor space you have to sweep on each one. Knowing there are ten floors tells you nothing about the total sweeping.
saying these in an interview costs you the question
- Says any recurrence that halves the input is O(log n)
- Counts the levels but never the work per level
- Thinks two subproblems merely double a constant
- Believes the base of the logarithm changes the class
- Ignores work done in helpers called before recursing