Why is Floyd's bottom-up heap build O(n) when a single sift-down costs up to O(log n)?

## The claim that needs rebutting Ask almost anyone why building a heap is O(n log n) and you get: "there are n elements, each one costs log n to place, so n log n." That reasoning is correct for a loop of inserts and wrong for the bottom-up build, and knowing precisely why is one of the most-asked heap questions there is. The error is not in the arithmetic; it is in the charge. `O(n log n)` really is an upper bound on the bottom-up build — big-O is an upper bound, and a loose one is still a true one — but it is not tight, and the tight bound is `Θ(n)`. ## Depth versus height Two quantities are easy to confuse. - A node's **depth** is its distance from the root. - A node's **height** is the distance from it down to the deepest leaf beneath it. Sift-**up** can travel as far as the node's depth. Sift-**down** can travel only as far as the node's height. In a complete binary tree these two are distributed in opposite directions: about half of all nodes are leaves, which have height 0 but maximum depth. The bottom-up build pays height; the insertion build pays depth. That single observation is the whole answer. ## The sum-of-heights argument In a complete tree of n nodes, the number of nodes at height `h` is at most `ceil(n / 2^(h+1))`. A node at height `h` performs at most `h` swaps during its sift-down. Total work is therefore bounded by the sum over all heights of (nodes at that height) x (their maximum cost): | height h | nodes at height h | max swaps each | contribution | |---|---|---|---| | 0 (leaves) | ~n/2 | 0 | 0 | | 1 | ~n/4 | 1 | ~n/4 | | 2 | ~n/8 | 2 | ~n/4 | | 3 | ~n/16 | 3 | ~3n/16 | | 4 | ~n/32 | 4 | ~n/8 | | ... | ... | ... | ... | | log n (root) | 1 | log n | log n | The contributions rise and then collapse. Summing them gives `n * sum over h of (h / 2^(h+1))`, and the infinite series `sum of h / 2^h` converges to 2, so the whole expression is bounded by about `n` swap steps. A convergent series is the mathematical shape of the answer: the levels near the bottom hold nearly all the nodes and cost nearly nothing, while the levels that cost a lot hold almost no nodes. Note what this is *not*. It is not an amortized argument in the accounting sense, and it does not depend on the input distribution. Every one of the n items is present when the loop starts; the bound is a worst-case bound over all inputs. ## Why the insertion build cannot be rescued the same way Run the mirror-image argument on repeated insertion. A node inserted when the heap already holds k items enters at the bottom and may sift up as far as `log k`. The nodes are not concentrated at cheap positions here — they are concentrated at *expensive* ones, since half of all positions are at maximum depth. The sum is `Θ(n log n)` in the worst case, and the worst case is real: feed items in an order where each arrival out-ranks everything already present (strictly decreasing keys into a min-heap, strictly increasing into a max-heap) and every single insert walks the whole way to the root. One honest refinement worth knowing: for *uniformly random* input, the insertion build averages `Θ(n)` too, because a random new item usually loses to its parent almost immediately. So a benchmark on shuffled data will show the two builds much closer than the asymptotics suggest. The difference between them is a worst-case guarantee versus an average that adversarial or merely sorted input destroys. Saying "the insert loop is O(n log n)" is correct as a worst-case claim; saying "it always takes n log n time" is not. ## What an interviewer is checking Three things. First, that you do not recite `n * log n` reflexively. Second, that you can name where the nodes are — the phrase "half the nodes are leaves" is the load-bearing sentence of the whole answer. Third, that you keep the direction of the claims straight: `O(n)` is the total for the build, not a promise about any single sift-down, which can still cost `log n` when the root is unlucky.