From "Introduction to Algorithms" - Cormen, Leiserson, Rivest, Stein - Third Edition pg. 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(n), since the stack size is at most n. The worst-case time of any stack operation is therefore O(n), and hence a sequence of n operations costs O(n^2), since we may have O(n) Multipop operations costing O(n) each. Although this analysis is correct, the O(n^2) result, which we obtained by considering the worst-case cost of each operation individually, is not tight."

"...since we may have O(n) Multipop operations costing O(n) each." This seems badly written: why would they count the number of some items in terms of running time, O(n)? The way I INTERPRET this is that a sequence of only N multipops(N) will result in O(n^2).. 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(n^2). Or perhaps what may help is if you can rewrite the problem statement... maybe that's what is confusing.

The problem : push,pop, multipop which cumulatively add up to N or is it N push, N pop and N multipop operations?

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?