Skip to main content

Why is a sequence of n Push, Pop, Multipop operations O(n²)?

From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453:

Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The worst-case cost of a Multipop operation in the sequence is $O\left(n\right)$, since the stack size is at most $n$. The worst-case time of any stack operation is therefore $O\left(n\right)$, and hence a sequence of $n$ operations costs $O\left(n^2\right)$, since we may have $O\left(n\right)$ Multipop operations costing $O\left(n\right)$ each. Although this analysis is correct, the $O\left(n^2\right)$ result, which we obtained by considering the worst-case cost of each operation individually, is not tight.

Part of this seems badly written:

[...] since we may have $O\left(n\right)$ Multipop operations costing $O\left(n\right)$ each.

Why would they count the number of some items in terms of running time, $O\left(n\right)$? The way I interpret this is that a sequence of only $n$ multipops(n) will result in $O\left(n^2\right)$, but after the first one, I imagine the stack is empty.

Someone try and explain how the worst case cost of a sequence of $n$ push, pop, multipop is $O\left(n^2\right)$. Or perhaps what may help is if you can rewrite the problem statement... maybe that's what is confusing.

Question: Do the push, pop, and multipop cumulatively add up to $n$, or is it $n$ push, $n$ pop, and $n$ multipop operations?