Why is dequeuing from the front of an array-backed queue O(n), and what does that cost a backlog?
answer
- picture the slots after the front leaves
- closing the hole costs what
- one dequeue touches how many slots
- n dequeues, each shifting nearly n
- the shifts sum to a square
basics
~20 sRemoving the element at index 0 slides every remaining element one slot toward the front, so a single dequeue costs O(n). Draining a backlog of n items that way costs about n^2/2 moves in total.
solid answer
~40 sA queue promises first-in, first-out order, and an array-backed one usually keeps the oldest record at index 0. Reading that record is genuinely O(1) — a contiguous block makes the address pure arithmetic — but *removing* it leaves a hole, and closing the hole copies every later element one slot left. That is O(n) per dequeue however fast indexing is. Enqueue at the back is the cheap end: amortized O(1) under growth doubling, even though one particular append copies the whole array. The asymmetry is what bites. Drain a backlog of n tickets and the shifting alone sums to roughly `n^2/2` element moves, so an intake service that is comfortable at fifty tickets collapses at fifty thousand. The fix is to stop moving data: advance a front index instead.
go deeper
Be ready to state FIFO and give the cost of each queue operation. The one being checked is removal at the front of an array-backed queue: say O(n), and say why — every later element moves one slot.
Explain the mechanic rather than the label: closing the hole at index 0 copies each later element left, and draining n items sums to about n^2/2 moves. Separate that clearly from the amortized O(1) append at the back.
Expect a service that behaved in staging and went quadratic under a production backlog. Show you would catch the front-removal in review before it ships, and name the fix — advance an index instead of moving the data.
Own the call about when the naive version is right. At small, provably bounded depth, contiguous shifting beats pointer chasing and simple code has real value; the decision turns on the depth during an incident, not on the asymptotics alone.
## The contract before the cost A queue is the first-in, first-out (FIFO) discipline: `enqueue` adds at the back, `dequeue` removes the oldest item from the front, `peek` reads the front without removing it. The interesting claim in any queue implementation is not that order is preserved — that part is nearly free — but that all three operations are **O(1)**. An implementation that keeps perfect FIFO order while making one operation O(n) is a *correct* queue and a *broken* one, and this is the most common way to break it. ## The scenario An intake service buffers support tickets — each record is a ticket id plus an arrival timestamp — in a plain dynamic array, oldest at index 0, newest at the end. Serving a ticket means taking element 0. Adding one means appending at the end. It reads as the obvious implementation, and it is quadratic. ## Why index-0 removal is O(n) Accessing element 0 is O(1). The array is one contiguous block, so the address of slot i is `base + i * elementSize` — arithmetic, not search. That constant-time *access* is exactly what makes the wrong answer tempting: people carry the O(1) from indexing over to removal. Removal is a different operation. After element 0 leaves, slots 1..n-1 still hold their elements, but the array's whole contract is that the item logically at position i lives in slot i. Closing the hole means copying element 1 into slot 0, element 2 into slot 1, and so on — **n-1 moves for one dequeue**. Nothing about the copy is clever or avoidable; it is the price of keeping the positional invariant. ## The arithmetic of a backlog One dequeue costing O(n) is survivable. Draining a backlog is not. With n items queued, the first dequeue shifts n-1 elements, the next shifts n-2, and so on: ``` (n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2 ``` That is Θ(n^2) element moves to drain the queue once. Quadratic is not "a bit slower"; it is a different shape. Ten times the backlog is a hundred times the shifting. This is why the defect hides so well: at the queue depths you see in a test — a few dozen tickets — the array version is not merely acceptable, it is often the *fastest* option, because contiguous copying is cache-friendly and involves no pointer chasing. The bill arrives the first time an incident lands and depth jumps by three orders of magnitude, and it arrives as a service that is pegged rather than as a crash you can read. ## The other end is fine Appending at the back writes into slot `count` and increments the count — O(1) — until the array is full, at which point a growth-doubling implementation allocates a larger array and copies everything once, an O(n) event. Spread over the appends that paid for it, that is **amortized O(1)**. Two precisions matter here, because both are routinely stated backwards: - Amortized O(1) does **not** promise any single append is fast. One particular append copies the entire array. The promise is about the *total* over a worst-case sequence: n appends cost O(n) together. - Amortized is **not** average-case. Average-case assumes a distribution over inputs; amortized makes no probabilistic assumption at all and bounds a worst-case sequence. ## What actually fixes it The fix is not a faster copy — it is not copying. Stop treating "the front of the queue" as "slot 0 of the array" and keep a `head` index instead. Dequeue reads `a[head]` and increments `head`: O(1), with no element moved. That alone leaks the abandoned prefix, so the practical realization wraps both indices around the array modulo its capacity, reusing the freed slots — the circular-array queue. A linked-node queue, holding a reference to each end, gets the same O(1) at both ends by different means, trading contiguity and cache locality for the freedom never to move anything. ## Keep the direction of the claim right O(n) per dequeue is an upper bound on how the cost *grows*, not a verdict that the code is slow today. If the queue provably never exceeds a few dozen entries, the naive version is a reasonable, readable choice and asymptotics do not decide it. What decides it is the answer to "what is the depth when something goes wrong upstream?" — because that is when the queue is deepest and the service is least able to afford quadratic work.
- Would reserving spare capacity at the end of the array fix the dequeue cost?No. Spare capacity at the tail only makes enqueue cheaper by delaying the next grow-and-copy; the front removal still slides every stored element one slot left. The dequeue cost is caused by the positional invariant, not by the allocation, so you fix it by not moving data — advance a front index rather than compact the array.
- The queue never exceeds forty tickets. Does the quadratic behaviour matter then?Barely. Forty squared is nothing, and contiguous shifting is cache-friendly enough that the simple version can beat a pointer-chasing one at that size. Asymptotics describe growth, not small-n speed. The reason to still care is that intake queues rarely stay at forty: the depth you must survive is the one during an incident, which is exactly when quadratic work is unaffordable.
- If both enqueue and dequeue happened at the array's end, would order still be FIFO?No — adding and removing at the same end is last-in, first-out, which is a stack, not a queue. FIFO requires the two operations to act on opposite ends, and that requirement is precisely what forces an array-backed queue to make one end awkward unless you let the indices move instead of the data.
Everyone in a ticket line shuffles one step forward each time the person at the front is served. Serving one person costs the entire line a step.
saying these in an interview costs you the question
- Removing from the front of an array is O(1)
- Indexing is constant time, so removal must be too
- Amortized growth hides the cost of the shifting
- It is only slow on huge inputs, so it never matters
- Arrays are always the wrong backing store for a queue