Why do two sequential loops over n records cost O(n), but one nested inside the other O(n^2)?

## The two composition rules Almost all iterative complexity analysis reduces to two rules about how loop costs compose. **Sequential composition adds.** If one block costs `f(n)` and the block after it costs `g(n)`, running both costs `f(n) + g(n)`. Since big-O keeps only the dominant term and drops constant factors, `n + n = 2n` is O(n), and `n^2 + n` is O(n^2) — the linear pass is invisible next to the quadratic one. **Nested composition multiplies.** If a loop runs `a` times and its body costs `b` each time, the total is `a * b`. An inner loop nested in an outer one restarts from scratch on every outer iteration, so its full cost is paid `a` times over. ## Why the multiplication is the surprising one A loop that runs n times and does constant work per pass costs O(n) — this feels obvious. The trap is that people count *loops in the source text* rather than *executions of the innermost statement*. Consider a nightly job over n settled payments: - Pass 1 normalises every record. Pass 2 sums every record. Pass 3 writes every record. Three loops, three passes over the data, `3n` operations, O(n). Tripling the record count triples the runtime. - Now instead put the summing loop *inside* the normalising loop. The source has the same two loops, but the sum is recomputed for every single record: `n * n` operations. Tripling the record count makes it **nine** times slower. That difference — a factor of 3 versus a factor of 9 for the same input growth — is what the notation is trying to communicate, and it is entirely determined by whether one loop is beside the other or inside it. ## Counting the innermost body The reliable method is mechanical: walk from the outside in, and for each loop write down how many times it runs *given* the loops enclosing it. Multiply down a nesting chain, add across siblings. For a loop over n regions, each containing a loop over the m stores in that region: ``` total = sum over regions of (stores in that region) ``` If every region has m stores, that is `n * m` — and note this is O(n*m), **not** O(n^2), because n and m are independent inputs. Collapsing two different sizes into one symbol is a common early mistake: if there are 10,000 regions and 3 stores each, calling it "quadratic" wildly misdescribes the work. State the bound in terms of every input that actually varies. ## Constants, and why they are dropped but not irrelevant Big-O deliberately discards the constant: O(2n), O(3n) and O(n/2) are all written O(n), because the notation describes how cost *scales* with input size, not how many nanoseconds it takes. Three sequential passes really is three times more work than one — but both triple when the input triples, so they belong to the same growth class. Say "three linear passes, O(n)" rather than "O(3n)"; the first is precise about both facts. The reverse error matters more: a candidate who has learned "drop constants" sometimes concludes that constants never matter. They do — they just do not change the class. Merging three passes into one is a real, worthwhile optimisation when the data is large and each pass touches memory; it is simply not a complexity improvement, and it will never rescue an accidentally quadratic loop. ## What an interviewer is checking They want to hear the two rules named, applied to the fragment on the whiteboard, and stated in terms of the innermost body's execution count. The strong answer also flags when the two loop bounds are different inputs, and does not inflate a sequence of passes into a higher power. Being able to say "this is O(n^2) because the inner loop restarts for each of the n outer steps, so the comparison runs n times n" is the whole of what is being asked.