Suppose we perform a sequence of stack operations on a stack whose size never exceeds k. After every k operations, we make a copy of the entire stack for backup purposes. Show that the cost of n st...

The question is:

"Suppose we perform a sequence of stack operations on a stack whose size never exceeds k. After every k operation, we make a copy of the entire stack for backup purposes. Show that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized costs to the various stack operations."

We will assign the following amortized costs:

Push uses one credit to pay for itself and saves one credit for future pops and one for copying the stack. Pop and Multipop pay for their operations using saved Push credits and save a credit for stack copying. After k operations, we have saved k credits exclusively for stack copying and can copy the stack for free. Since each operation costs at most O(1) amortized and the credits are nonnegative, the cost for n operations is O(n).