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?