Why does T(n)=2T(n/2)+O(n^2) total Θ(n^2) rather than Θ(n^2 log n)?

## Where such a recurrence comes from The attached fragment rolls a file listing up a balanced directory tree, and at each directory it removes duplicates by comparing every collected file against every file kept so far. Two recursive calls, each covering about half the files; a combine step that is quadratic in the number of files the call is handling. That is `T(n) = 2T(n/2) + O(n²)` and it is the shape of a whole family of real defects: a merge step that does a nested scan, an aggregation that re-sorts by comparing all pairs, a validation that cross-checks every collected item against every other one. The seductive wrong answer is "quadratic work, logarithmic depth, so n² log n". It over-charges, and the reason it over-charges is worth understanding, because the same reasoning error goes the other way in other recurrences and *under*-charges there. ## Sum the tree by levels Level i of the tree holds 2^i calls, each on about n/2^i files. Each of those calls does work proportional to the *square* of its own input: > level i cost = 2^i × c·(n/2^i)² = c·n²/2^i So the level costs run c·n², c·n²/2, c·n²/4, c·n²/8, … Squaring shrinks the per-node work by four while the node count only doubles, so half the work disappears with every level down. Summing the whole tree: > c·n²·(1 + ½ + ¼ + ⅛ + …) < 2c·n² The entire recursion costs less than twice what its single top-level call costs on its own. The total is **Θ(n²)**, and the number of levels never enters the arithmetic. This is a *root-dominated* tree. ## The three regimes, and the rule they replace Every recursion tree falls into one of three shapes, and you must identify which one before you compute anything: | Level costs as you descend | Dominated by | Total | |---|---|---| | Shrink geometrically (n², n²/2, n²/4 …) | the root | Θ(root work) | | Stay flat (n, n, n …) | nothing in particular | Θ(level work × depth) | | Grow geometrically (1, 2, 4 … up to n) | the leaves | Θ(leaf work) | "Multiply per-call work by the depth" is the middle row only. Applying it to the top row over-charges by a log factor, which is the error in this question. Applying it to the bottom row is where people miss that a constant-work-per-call binary recursion is already linear because of its leaf count. The habit worth building is: compute the level costs, look at their *ratio*, and only then decide whether to multiply or to sum a series. A quick way to spot the regime without writing the series: compare one call's own work against the total work of its children. Here a call on m files does c·m², and its two children do 2·c·(m/2)² = c·m²/2 — half as much. Any time a parent out-works all of its children combined by a constant ratio, the tree is root-dominated and the answer is just the root's own work. ## What this changes in practice **Where the time shows up.** Because the root accounts for more than half the run, a sampled profile points squarely at the outermost invocation, not at a hot leaf. Engineers used to leaf-dominated recursions sometimes distrust that profile and go hunting deeper. Trust it: in a root-dominated tree the profile is telling the truth, and the top frame really is the workload. **Which optimisation pays.** Three tempting changes, and only one of them matters: - *Raising the base-case cutoff* so small directories are handled directly — trims levels off the bottom, where less than a thousandth of the work lives. Nearly worthless here, even though it is a genuine win in flat-level recursions. - *Reducing the branching factor or balancing the tree better* — changes the depth, which does not appear in the answer at all. - *Making the combine step cheaper* — changes the root's own work, which **is** the answer. Deduplicating by identity through a hash-based set makes the combine linear, turning the recurrence into `T(n)=2T(n/2)+O(n)` and the whole run into Θ(n log n). Keeping the sublists sorted and merging them also gives a linear combine. Either way the fix is at the top, not the bottom. **Why the bug survives review.** Each call looks locally reasonable — a nested loop over "just this directory's files". The quadratic only becomes visible when you notice that the list a call handles grows with the whole subtree, so the outermost call's inner loop runs over all n files. Writing the recurrence down is exactly the discipline that surfaces it: f(n) is whatever this call does to its own input, and here that is n² at the root. ## Stating it in an interview "Level i does n²/2^i work, the series sums to about 2n², so it's Θ(n²) and the root dominates — the depth doesn't matter here. If I want a real speedup I have to attack the combine step, not the recursion." That answer shows you sum trees rather than pattern-match them, and it lands the operational point that the fix belongs at the top of the tree.