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

Question

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?

Answer 1

First, let me comment on 2 misconceptions I see in your question:

1. Landau notation ('Big $O$ notation') does not exclusively refer to running times, we can use it to describe any function we wish.
2. The fact that the worst case running time is $O(n^2)$ doesn't mean the running time isn't also $O(n)$.

The second part comes close to the point of this part in the book. The authors first show that a (crude) analysis of executing the multi-pop operation $n$ times: worst case of a single multi-pop is $O(n)$, we pop $n$ times, so we spend at most $O(n^2)$.

However, do all of our $n$ multi-pop operations require $O(n)$ time? The authors continue to show that using the aggregate analysis that this isn't the case, by which they obtain a sharper bound of $O(n)$ for $n$ multi-pop operations.

So, in this section, the authors show the utility of aggregate analysis by the multi-pop example.

As for the part labeled as 'question': yes, the total running time of all $n$ operations is $O(n)$, as the book describes in the next section:

We can pop each object from the stack at most once for each time we have pushed it onto the stack. Therefore, the number of times that POP can be called on a nonempty stack, including calls within MULTIPOP , is at most the number of PUSH operations, which is at most $n$