In a same-direction two-pointer sweep over one array, why is the cost O(n) and not O(n^2)?

## What the sweep looks like A same-direction two-pointer sweep walks a single sequence with two indices that both travel toward the end. One index — call it `fast` — visits every position in turn and does the reading. The other — call it `slow` — advances only when something worth keeping happens: a value survives a filter, a run of equal keys ends, a compacted prefix grows by one. Both start near the front and **neither ever moves backward**. Because two index names appear in the code, the shape gets misread as "a loop inside a loop", and the reflexive answer is O(n^2). It is not, and the reason is worth being able to say precisely. ## The counting argument Cost is the number of elementary steps, so count them directly: - `fast` starts at some position near 0, increases by one per iteration, and stops at `n`. It therefore increments at most `n` times over the entire run. - `slow` starts near 0, only ever increases, and can never pass `fast`. It therefore also increments at most `n` times. - Each iteration performs a fixed amount of work: one comparison, maybe one copy, maybe one increment of `slow`. Total work is bounded by a fixed constant times `(n + n)`, which is O(n). Notice what the argument never does: it never multiplies the two counts together. Multiplication is what nesting buys you, and nesting is characterised by an inner index that **restarts** — for every position of the outer index, the inner one walks a fresh range. Here there is one loop and two cursors that each walk the sequence at most once. Two forward walks **add**; they do not multiply. ## The invariant behind it The structural fact that keeps the sweep honest is `slow <= fast` at every step. Two consequences fall out of it: 1. **Correctness.** The region `[0 .. slow]` that has already been written is a prefix of the region `[0 .. fast]` that has already been read, so a write at `slow` can never land on a position the reader has not yet consumed. 2. **Cost.** Since `slow` is pinned below a value that only reaches `n`, it cannot itself exceed `n` increments. The bound on one cursor is inherited by the other. Being able to state that invariant out loud is usually the real thing being tested; the complexity answer follows from it in one sentence. ## What would break the bound The argument depends on **monotonicity**. If either index is ever decremented or reset, the counting collapses and the true cost has to be re-derived. A sweep that rewinds the scanning cursor back to just after the write frontier on every mismatch is a genuinely different algorithm — that restart is exactly the structure of naive repeated scanning, and it really can hit O(n^2) on adversarial input. When a candidate is asked whether a piece of code is a linear sweep, the check is mechanical: does any index ever move left? If not, it is linear. A related trap: work inside the loop that is not O(1). If each iteration performs a linear operation — copying a whole block, searching a region — the outer count is still `n`, but the total is `n` times the inner cost. The linearity claim is about **two monotone cursors plus constant-time bodies**, and both halves matter. ## Worst case, not amortized, not average Three bounds get muddled here, and the distinction is a common follow-up: - **Worst case** — the maximum over all inputs of size `n`. This is what the sweep has: every input costs at most about `2n` steps. - **Amortized** — the cost of an operation averaged over a worst-case *sequence* of operations, used when a rare step is expensive (growth-doubling containers pay for occasional full copies this way). Nothing here is rare-and-expensive, so no amortization is involved. - **Average case** — assumes a probability distribution over inputs. Not needed either; the sweep has no input-dependent blow-up to average away. Saying "it's amortized O(n)" is a small answer that signals a big confusion, and interviewers listen for it. ## Space, and the honest caveats Auxiliary space is O(1): two integers. The sweep is iterative, so there is no recursion stack to count — worth remembering that recursion depth *is* space, and a recursive rewrite of the same logic would carry an O(n) stack unless the compiler eliminates the tail call. Finally, asymptotics are an upper bound and say nothing about the constant. A linear sweep touching every element still reads `n` elements from memory; when the survivors are few and the sequence is huge, the constant factor of the copies — not the O(n) label — is what a profiler will show you.