Why is a stack-based delimiter scan with a nested pop loop O(n) and not O(n^2)?
answer
- Multiplying the two worst cases double-counts
- Ask what the inner loop consumes
- Charge each inner iteration to one pop
- A token enters the stack at most once
- Total pops cannot exceed total pushes
basics
~20 sBound the total work, not the worst inner-loop length. Each token is pushed at most once and popped at most once, so every inner-loop iteration across the entire scan is charged to a distinct pop — at most n of them overall.
solid answer
~50 sThe quadratic reading multiplies the outer loop's n iterations by the inner loop's worst length, but those two worst cases cannot both occur n times. Charge each inner iteration to the token it pops. A token is pushed at most once, during its own outer iteration, and once popped it never comes back, so across the entire scan there can be at most n pops. Total work is the n outer steps plus at most n pops — O(n) — even though one unlucky outer iteration might pop hundreds of entries. This is the aggregate argument in its most common disguise: bound the total number of times an element can move, rather than the worst cost of a single step. Whenever an inner loop consumes a resource that is produced at most once per element, suspect linear rather than quadratic.
code
pseudocode · 12 lines// t[0..n-1] is the token stream; the stack holds open delimiters
stack = empty
for i in 0..n-1
if is_open(t[i])
push(stack, t[i])
else
while not empty(stack) and not matches(top(stack), t[i])
pop(stack) // discard a group left unclosed
if empty(stack)
report_error(i)
else
pop(stack) // matched pair closedgo deeper
Recognise that a loop inside a loop is not automatically quadratic, and be able to say that each token here is handled a bounded number of times no matter how the input nests.
Be ready to run the charging argument aloud: each inner iteration is paid for by one pop, pops are bounded by pushes, and pushes are bounded by the number of tokens.
Show that you apply this test while reviewing code — identify what the inner loop consumes and how it is replenished. A per-outer-iteration refill is the whole difference between linear and quadratic.
The value here is teaching the test so reviewers stop rejecting linear code because it looks nested, and start catching the genuinely quadratic loops hiding behind the identical shape.
A validator walks a token stream and checks that nested delimiters are properly closed. Opening delimiters are pushed; a closing one pops entries until it finds its partner, discarding groups that were left unclosed. The loop body contains a loop, so the reflex reading is O(n^2). That reading is wrong, and the reason it is wrong is one of the most frequently reused arguments in interview complexity analysis. ## Why multiplying the worst cases overcounts The naive bound says: the outer loop runs n times, the inner loop could run up to n times, therefore n^2. Each half of that sentence is individually true, and the conjunction is still an enormous overcount, because the two events are not independent. For the inner loop to run n times on one outer iteration, the stack must hold n entries, which requires n earlier outer iterations that pushed and did *not* pop. Every deep inner loop must be financed by a long stretch of shallow ones. The worst cases exclude each other. ## The charging argument Rather than bounding the inner loop per outer iteration, bound the inner loop's iterations *in total*, across the whole run: 1. Every inner iteration performs exactly one pop. 2. Every pop removes an element that was previously pushed, and that element does not return. 3. Pushes happen at most once per outer iteration, so there are at most n pushes. 4. Therefore there are at most n pops in total, so the inner loop runs at most n times summed over the entire scan. Total work is n outer steps plus at most n pops, which is O(n). The per-token cost is amortized: handling one token can cost Θ(n), and the sequence still costs O(n). This is aggregate analysis — total the work by category (pushes, pops) instead of by call. ## The test to apply to any nested loop When you see a loop inside a loop, ask two questions: - **What does the inner loop consume?** Here, stack entries. - **How is that resource replenished?** Here, at most once per outer iteration, by a push. If the resource is produced at most a constant number of times per outer iteration and each unit is consumed at most once, the total inner work is linear and the whole thing is O(n). If the inner loop instead re-examines a collection that is refilled — or never drained — every time round, the multiplication is real and the code is genuinely quadratic. That single test separates the two-pointer, sliding-window and stack-scan family from actually quadratic code that happens to look the same on the page. ## Where it goes wrong The argument depends on elements not re-entering the structure. Change the inner loop so that popped entries are pushed back, or so that it inspects the stack from the bottom without removing anything, and the linear bound is gone: an element can now be visited an unbounded number of times, the pushed-once accounting collapses, and the n-times-n reading becomes accurate. The lesson generalises: the bound is not a property of the loop shape, it is a property of the movement budget of the elements. ## Amortized per element, worst case for the scan A subtlety worth stating explicitly in an interview. The *scan as a whole* is worst-case O(n): no input makes it slower, so this is a hard bound on the batch, not a probabilistic or average claim. It is only the *per-token* cost that is amortized. That composition — amortized per operation, flat worst case for the sequence — is exactly what an amortized bound buys you, and it is why an amortized structure is a perfectly safe choice inside a batch job even when it would be a poor choice on a latency-critical request path. ## Communicating it Saying "it is O(n) because each element is pushed once and popped once" is the compressed form, and it is what an interviewer wants to hear. Being able to unpack it — what is charged to what, why the two worst cases cannot coexist, what would have to change for the code to be genuinely quadratic — is what separates a memorised phrase from an argument you can apply to unfamiliar code.
- What would you have to change in this loop to make it genuinely quadratic?Give the inner loop a resource that is replenished on every outer iteration — push the popped tokens back afterwards, or have the inner loop read the whole stack from the bottom without removing anything. Once an element can be visited an unbounded number of times, the pushed-once charging argument collapses and the n-times-n reading becomes real.
- Is the O(n) result here an amortized bound or a worst-case one?Both, at different granularities. The whole scan is worst-case O(n) — no input makes it slower. It is only the per-token cost that is amortized, since one token's handling can be Θ(n). That composition is typical: amortized per operation, flat worst case for the batch, which is why amortized structures are safe inside batch jobs.
saying these in an interview costs you the question
- Assumes nested loops always mean quadratic time
- Multiplies outer n by the worst inner length
- Cannot say what resource the inner loop consumes
- Claims the bound depends on typical nesting depth
- Counts pops per outer iteration instead of in total