Why is a grow-right/shrink-left sliding window O(n) overall when a shrink while-loop sits inside the main loop?

## The wrong instinct, stated precisely The code has a `while` inside a `for`, and the reflex analysis multiplies: `n` outer iterations times up-to-`n` inner iterations equals O(n²). The multiplication is where the reasoning breaks. Multiplying assumes the inner loop can do its worst *on every* outer iteration independently. Here it cannot, because the inner loop consumes a resource that never replenishes: forward positions of the left pointer. ## The aggregate (amortized) argument Count pointer movements rather than loop iterations: - The right pointer starts at the first element and advances once per outer iteration. Over the whole run: at most `n` moves. - The left pointer starts at position 0, advances by one on each inner-loop iteration, and **never moves backward**. It cannot pass the right pointer by more than one. Over the whole run: at most `n` moves. Every unit of work in the scan is attached to one of these moves — an admission on a right-move, an eviction on a left-move. So the total number of admissions plus evictions is at most `2n`, regardless of how the evictions cluster. Equivalently: **each element enters the window at most once and leaves it at most once.** An element that has been evicted is never seen by the inner loop again. Concretely, in a packet-trace scan for the longest burst with at most `k` distinct sources, the trace can be adversarial — long quiet stretches, then a new source that forces the window to collapse almost entirely in one iteration. That one iteration is expensive. But it *spends* left-pointer moves that the rest of the scan now cannot spend: the total across all bursts still cannot exceed `n` evictions. ## Amortized is not average Two distinctions interviewers listen for: 1. **Amortized vs per-operation.** The O(n) total does *not* mean each outer iteration is O(1). A single iteration can evict a large fraction of the window. The guarantee is about the worst-case **sum** over the whole sequence of operations. 2. **Amortized vs average-case.** Average-case analysis assumes a probability distribution over inputs and can fail on unlucky ones. The `2n` bound here holds for **every** input, including adversarial ones — no randomness, no distributional assumption. Calling this "average" is the classic misuse of the word. ## What the bound actually covers The pointer argument bounds the *number* of admissions and evictions at `2n`; it says nothing about their *cost*. Total time is O(n × cost-per-update): | Per-move bookkeeping cost | Overall scan | |---|---| | O(1) worst-case (running sum, counter) | O(n) worst-case | | O(1) expected (typical hash-based counts) | O(n) expected | | O(log n) (ordered structure per move) | O(n log n) | Stating the bound as "O(n) expected" when hash-based state is involved, rather than a flat "O(n)", is the kind of precision that distinguishes a middle-level answer. ## What would genuinely make it quadratic The linearity is a property of the discipline, not of the pattern's name, and two implementation mistakes break it: - **Recomputing from scratch.** If, instead of updating state incrementally on each move, the code rescans the whole window to re-derive its statistics after every edge move, each of the O(n) moves costs O(n), and the scan is O(n²). - **Backtracking the left pointer.** Any variant that moves `left` backward — for instance, restarting the window at an earlier position after a violation — destroys the "each element leaves at most once" accounting, and the 2n cap with it. Both show up in real code more often than the textbook version does, which is why the argument is worth being able to reproduce on demand rather than merely quote.