top of page

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).

23 views0 comments
logo

Crookshanks Academy is an online learning platform with free netflix styled courses.

Crookshanks Academy 2023 ©️ All Rights Reserved

This content is protected from right clicks.
bottom of page