Amortized Analysis IV

[hamidgasmi]

Imagine a stack with a new operation: PopMany which takes a parameter, i, that specifies how many elements to pop from the stack. The cost of this operation is i, the number of elements that need to be popped.

Without this new operation, the amortized cost of any operation in a sequence of stack operations (Push, Pop, Top) is O(1) since the true cost of each operation is O(1).

What is the amortized cost of any operation in a sequence of n stack operations (starting with an empty stack) that includes PopMany (choose the best answers)?

(1) O(1) because the sum of the costs of all PopMany operations in a total of n operations is O(n)
(2) O(n) because we could push n−1 items and then do one big PopMany(n−1) that would take O(n) time
(3) O(1) because we can define Φ(h)=size
(4) O(1) because we can place one token on each item in the stack when it is pushed. That token will pay for popping it off with a PopMany
(5) O(n) because we could push n−1 items and then do one big PopMany(n−1) that would take O(n) time

[hamidgasmi]

Answers: (1), (3) and (4)

---

Explanation:

• (1): Since over n operations starting with an empty stack there can be at most n items in the stack, the sum of the costs of the PopMany operations can be at most n. Thus, the total actual costs of n operations is at most O(n), so the amortized cost is O(n)/n=O(1).

---

• (2): Wrong:
  • It's not an amortization cost
  • O(n) is the amortization cost of the operation PopMany alone
  • Amortized Cost = Sum Cost(i)/n = [O(n) for n-1 pushes + O(n) for 1 PopMany]/ n = O(n) / n = O(1)
  • Amortized Cost = O(1)

---

• (3): Φ(hi) = size(hi)
  • Φ(h0) = 0
  • Φ(hi) ≥ 0
  • Amortized Cost = Cost(i) + Φ3(hi) - Φ3(hi-1):
    • When the i-th operation is Top:
      - Cost(i) = 1
      - size(hi) = size(hi-1)
      - Top Amortized Cost = 1
    • When the i-th operation is Push:
      - Cost(i) = 1
      - size(hi) = size(hi-1) + 1
      - Amortized Cost = 1 + size(hi-1) + 1 - size(hi-1) = +2
      - Push Amortized Cost = +2
    • When the i-th operation is Pop:
      - Cost(i) = 1
      - size(hi) = size(hi-1) - 1
      - Amortized Cost = 1 + size(hi) - (size(hi) + 1) = 0
      - Pop Amortized Cost = 0
    • When the i-th operation is PopMany:
      - Cost(i) = size(hi-1) - size(hi)
      - Amortized Cost = size(hi-1) - size(hi) + size(hi) - size(hi-1) = 0
      - PopMany Amortized Cost = 0
  • Therefore Φ shows that the amortized cost is O(1)

---

• (4): Place a token for each newly-pushed element. Then, on a PopMany operation, use the token of each popped element to pay for its popping cost. Therefore, the amortized cost is 2 which is O(1).

---

• (5): see explanation of (2)