A left and right index converge over a timestamp log with swaps inside — why is that loop O(n), not O(n^2)?
answer
- stop counting loops, count moves
- each index moves one direction only
- how far can both indices travel?
- total movement bounds the iteration count
- the gap starts at n-1 and only shrinks
basics
~20 sEvery iteration moves at least one index, each index moves in only one direction, and together they can cover at most n positions before meeting. So the loop runs at most n times, whatever the body does per pass.
solid answer
~50 sCount movement, not nesting. The left index only ever increases, the right index only ever decreases, and the loop ends when they cross — so their combined travel is bounded by n positions. Every iteration advances at least one of them, which makes the iteration count at most n, and with constant work per pass the sweep is Θ(n). The rigorous form is a decreasing measure: the gap `right - left` starts at `n-1`, strictly decreases every iteration, and the loop stops at zero, so there are at most `n-1` iterations. A swap inside costs O(1) and does not change the count. The argument is fragile in one specific way: it dies the moment an index can be reset backwards or an inner scan restarts from a fixed point, which is exactly what turns a look-alike sweep quadratic.
code
pseudocode · 14 linesleft = 0
right = length(t) - 1
while left < right
if t[left] < cutoff
left = left + 1
else if t[right] >= cutoff
right = right - 1
else
swap(t[left], t[right])
left = left + 1
right = right - 1
// every branch shrinks (right - left); it starts at n-1
// and never grows, so at most n-1 iterations rungo deeper
Recall that a single loop with two indices moving toward each other passes over the data once. Be able to say the loop stops when the indices meet.
Explain the bound by counting movement: each index moves in one direction, both together cover at most n positions, so the iteration count is at most n. Multiply by the per-iteration work to get the total.
State it as a strictly decreasing measure and give the termination proof alongside the bound. Name the concrete change — a reset, or an inner rescan — that would turn the same loop quadratic, and check every branch for guaranteed progress.
Decide when a clever in-place sweep is worth its review burden versus a plainer two-pass version, and make the invariant an explicit, testable comment so the bound survives the next person who edits a branch.
## The fragment Here a day's event log is being partitioned in place so that everything before a cutoff timestamp ends up at the front: ``` left = 0 right = length(t) - 1 while left < right if t[left] < cutoff left = left + 1 else if t[right] >= cutoff right = right - 1 else swap(t[left], t[right]) left = left + 1 right = right - 1 ``` A reader who counts loop keywords sees one `while` and concludes linear; a reader who sees swaps and two moving indices sometimes suspects elements are being revisited and guesses quadratic. Neither is a counting argument. The counting argument is about **total index movement**. ## The monotone-progress argument Three observations settle it: 1. `left` never decreases and `right` never increases — each index moves in exactly one direction. 2. Every branch of the body moves at least one index by one position. 3. The loop terminates as soon as `left` meets or passes `right`. Together, the two indices start `n-1` apart and consume that distance one step at a time, never giving any of it back. Therefore the body executes at most `n-1` times. With O(1) work per iteration, the sweep is Θ(n) and touches each position a bounded number of times. The crisp way to say this in a review is as a **decreasing measure**: define `gap = right - left`. It starts at `n-1`, it strictly decreases on every iteration (by one in the single-move branches, by two in the swap branch), and the loop exits when it reaches zero or below. A quantity that starts at `n-1`, strictly decreases, and is bounded below can only decrease `n-1` times. That is a proof, not an intuition, and it is the form worth reaching for whenever a loop's trip count is not obvious from its bounds. ## Why "there is a swap inside" is a red herring Swapping two elements is constant work; it does not re-examine anything and it does not move any index backwards. The general rule is that the body's *cost per iteration* and the loop's *iteration count* are separate factors that get multiplied at the end. Conflating them is the usual source of both errors here: seeing constant-time work and concluding the loop is fast, or seeing data being rearranged and concluding it must be quadratic. What *would* change the total is a body whose cost is not constant — a scan, a sort, or a lookup that itself walks a range. Then the total is `iterations * cost-per-iteration`, and a linear body would make this Θ(n^2) despite the linear iteration count. ## What breaks the argument The argument rests entirely on monotonicity, and it is worth being able to say precisely how it fails, because look-alike code is common: - **A reset.** If any branch sets `left = 0` again, the index no longer moves in one direction, the measure no longer decreases, and the worst case becomes Θ(n^2) — or, if no branch guarantees progress, an infinite loop. - **An inner scan from a fixed anchor.** A nested `while` that walks from `left` forward looking for something, starting over each outer pass, re-covers the same ground repeatedly. The outer loop is still linear; the total is not. - **A branch that moves nothing.** If some condition path leaves both indices where they are, iterations are no longer bounded by movement at all, and the loop may not terminate. Every branch guaranteeing progress is a precondition of the argument, not a detail. Because of that last point, the review checklist for a converging sweep is short and mechanical: does every branch move an index; does any branch move one backwards; is the per-iteration work constant. Three yes/no answers give you both the bound and the termination proof. ## Why seniors are asked this The pattern shows up constantly in code that looks nested but is not, and the failure mode in review is confident hand-waving in either direction. What distinguishes a strong answer is that it does not appeal to familiarity with the shape — it names the measure, shows it decreasing, bounds the number of decreases, multiplies by the per-iteration cost, and then states the condition under which the whole argument would collapse. That same machinery transfers directly to any loop whose bound is implicit rather than written in the header.
- How would you state the O(n) claim in a review without hand-waving?Name a decreasing measure. The gap right minus left starts at n-1, strictly decreases on every branch of the body, and the loop exits at zero, so at most n-1 iterations run. Multiply by the constant work per iteration to get Θ(n). That form is a proof and it doubles as the termination argument.
- The same two indices, but an inner loop rescans forward from left on every pass. What is the cost?The monotone argument no longer applies to the body, and the worst case is Θ(n^2). The outer iteration count is still bounded by index movement, but the per-iteration work is now linear, and total cost is iterations times work per iteration. Trip count and body cost are separate factors; only their product is the answer.
- What single property must every branch of the body have for this bound to hold?Each branch must advance at least one index, and never move one backwards. If a branch can leave both indices unchanged the loop may not terminate at all; if a branch resets an index, the measure stops decreasing and the count is no longer bounded by n. Those two checks are the whole review of the pattern.
saying these in an interview costs you the question
- Guesses quadratic because elements are being swapped and rearranged
- Argues linear from the shape being familiar, with no counting
- Ignores whether every branch actually advances an index
- Assumes constant per-iteration work without checking the body
- Cannot say what change would make the same loop quadratic