A report loop sorts the whole transaction set on every row — what is the total cost?

## The scene A monthly report generator walks the rows it must emit, and for each row it needs a ranking over the month's transactions — the middle value, the top few, a percentile. The straightforward code puts the ranking where it is needed: ``` for i in 0..n-1: row = rows[i] ranked = sort(transactions) // same input on every pass row.midpoint = ranked[length(ranked) / 2] ... ``` One loop, a handful of statements. It reads as linear. It is not. ## The rule: per-iteration costs multiply The cost of a loop is (number of iterations) × (cost of one iteration), and the cost of one iteration includes every call it makes. A comparison sort over `m` items is O(m log m) — and that bound is not a pessimistic guess, it is close to the floor, because any sort that only compares elements needs Omega(m log m) comparisons in the worst case. So: `total = n × O(m log m) = O(n · m log m)` The two classic errors here are (1) *adding* instead of multiplying — "O(n + m log m), the loop plus the sort" — which is what you get if you think of the sort as happening once, and (2) assuming a repeated call on unchanged input is somehow cached. Nothing memoises a library call for you; each pass re-does the work. If the report emits one row per transaction, `n = m` and the expression collapses to **O(n^2 log n)**. That is worse than quadratic, for a job whose honest content is one sort plus one linear walk. ## Why this one is easy to miss The hidden cost here is different in flavour from a linear membership scan. There, the searched collection grew, so the badness accumulated visibly. Here every pass costs exactly the same, which is precisely why nobody notices: the profile shows a uniform hot line, the code looks regular, and small test fixtures finish instantly. The failure only shows up as the month gets busier, and it shows up steeply — double the transactions and the runtime goes up more than fourfold. ## The fix: hoist the loop-invariant work Ask of every expensive call in a loop body: *does its input depend on the loop variable?* If not, the call is **loop-invariant** and belongs above the loop. ``` ranked = sort(transactions) // once mid = ranked[length(ranked) / 2] for i in 0..n-1: rows[i].midpoint = mid ... ``` Cost: O(m log m) once, plus O(n) for the loop — written as O(m log m + n). This is a strictly better algorithm, not a micro-optimisation: it changes the growth class. When the sort's input *does* depend on the row, hoisting is unavailable and you need a different lever: sort once by the dominant key and derive each row's view from the sorted order; maintain a heap or an order-statistics structure incrementally; or, if you only need the k-th element rather than the whole order, use a selection algorithm, which is O(m) expected rather than O(m log m). Needing one element out of an ordered arrangement is a strong hint you never needed the arrangement. ## The adaptivity trap A sharp candidate raises: many mainstream standard-library sorts are adaptive — a stable merge-insertion hybrid like Timsort detects existing ordered runs and finishes an already-sorted input in O(m) — so after the first pass, isn't the rest free? No. It is *cheaper*, not free. The per-pass cost falls from O(m log m) to O(m), so the total falls from O(n · m log m) to O(n · m): still quadratic when n and m grow together. Adaptivity lowers a constant-ish factor on the wrong algorithm; hoisting removes the repetition. The same reasoning applies to any superlinear helper called per iteration — building a lookup structure, re-deriving an aggregate, re-parsing a configuration. Read the loop body as a bill of materials, and multiply. ## Interviewer variations to expect - "The sort is on a slice whose length shrinks each pass." Then sum the per-pass costs instead of multiplying a constant: `sum over k of k log k` is O(m^2 log m) — still quadratic-and-a-log. - "What if the sort is not comparison-based?" A counting or radix sort over bounded integer keys is O(m + range) per pass, escaping the comparison lower bound, but again it is per pass; the multiplication survives. - "Is the space complexity affected?" A merge-based sort needs O(m) auxiliary space, but it is reclaimed each pass, so peak extra space stays O(m) rather than n times that — allocation churn, however, is real and repeated.