AlgoVerse

Stack with MULTIPOP (amortized analysis)

One MULTIPOP may remove many items and be expensive, but each item is popped at most once; so n operations cost at most 2n in total.

A stack with three operations: PUSH(x), POP and MULTIPOP(k), which removes up to k items from the top. One MULTIPOP can cost O(n), so you might think n operations cost O(n²).

Read the full explanation ↓
Input:
n=10PDF export

Positive numbers are PUSH and negative ones MULTIPOP: six PUSHes, MULTIPOP(4), two PUSHes and MULTIPOP(10). The total cost is 16 for 10 operations (8 pushes and 8 pops), under 2 × 10.

  1. def multipop_stack(ops):
  2. # A positive number pushes itself; −k pops up to k items at once (0 pops nothing).
  3. stack = []
  4. cost = 0
  5. for op in ops:
  6. if op > 0:
  7. stack.append(op)
  8. cost = cost + 1
  9. else:
  10. k = -op
  11. while stack and k > 0:
  12. stack.pop()
  13. k = k - 1
  14. cost = cost + 1
  15. return cost

Invariant: The total number of pops never exceeds the total number of pushes, so the total cost is at most twice the number of operations.

Start

503182139425-467768-109

Local variables

Orange = changed in this step

ops list

538192-476-10

Call stack

  1. multipop_stack()line 1
Step 1 of 77
Black = push, multipop · Orange = key steppush: 0/8 · multipop: 0/2 · pop: 0/8 · total: 0/1
    Explanation

    The idea

    A stack with three operations: PUSH(x), POP and MULTIPOP(k), which removes up to k items from the top. One MULTIPOP can cost O(n), so you might think n operations cost O(n²).

    Amortized analysis

    Each item is pushed once and popped at most once. So the total number of pops (even inside MULTIPOPs) is at most the number of pushes, and n operations cost at most 2n: O(1) amortized per operation.

    The potential method: let the potential be the number of items on the stack. PUSH raises it by one (amortized cost 2), and each pop spends one unit of potential (amortized cost 0).

    The input

    A positive number means PUSH that number, and a negative number −k means MULTIPOP(k).

    What to watch in the trace

    • The bars are the stack (the top is on the right). cost in the memory panel is the total so far.