The Nested Loop Lies

A monotonic stack scan has a while loop nested inside a for loop, and a single iteration of the outer loop can pop the entire stack. A candidate is asked why the whole scan is still $O(n)$ rather than $O(n^2)$ . Which justification is the one that actually proves it?

In practice the stack stays shallow because the values are unlikely to be sorted, so the average case is linear even though the worst case is quadratic

Every element is pushed exactly once and popped at most once, so the pops summed over the whole scan total at most $n$ , no matter how uneven they are

The stack depth is bounded by $O(\log n)$ , so the inner loop can run at most $O(\log n)$ times per element

The inner loop is dominated by the outer loop, which is $O(n)$ , so the nesting does not change the bound