Amortized Analysis III

[hamidgasmi]

Let's imagine we add support to our dynamic array for a new operation PopBack (which removes the last element). Calling PopBack on an empty dynamic array is an error.

PopBack reallocates the dynamically-allocated array to a new array of half the capacity if the size is ≤ the capacity / 4 . So, for example, if, before a PopBack the size were 5 and the capacity were 8, then after the PopBack, the size would be 4 and the capacity would be 8. Only after two more PopBack when the size went down to 2 would the capacity go down to 4.

We want to consider the worst-case sequence of any n PushBack and PopBack operations, starting with an empty dynamic array.

What potential function would work best to show an amortized O(1) cost per operation?

Φ1(h)=2×size−capacity
Φ2(h)=2
Φ3(h)=max(2×size−capacity,capacity/2−size)
Φ4(h)=max(0,2×size−capacity)

[hamidgasmi]

Answer: Φ3

---

Explanation:

• Φ1 isn't a valid potential function: let's imagine a scenario where starting from an empty array:
  • We add 5 elements: array size = 5 and capacity = 8
  • We remove then 2 elements: array size = 3 and capacity = 8
  • Φ1(hi)=2×3−8 = -2 < 0

---

• Φ2 isn't neither a valid potential function:
  • Φ2(h0) <> 0

---

• Φ3 is the correct answer:
  • Φ3(h0) = max(2 × 0 − 0, 0 / 2 − 0) = 0
  • Φ3(hi) ≥ 0 for all hi? Let's prove it by induction:
    • Let's assume that ∃ hi such that Φ3(hi) < 0
    • This means: 2×size(hi) − capacity(hi) < 0 and capacity(hi) / 2 − size(hi) < 0
    • In other words: capacity(hi) ≥ 2 × size(hi) and capacity(hi) < 2 × size(hi)
    • contradiction!
  • Amortized Cost = Cost(i) + Φ3(hi) - Φ3(hi-1)
    • When Size(hi) < Capacity(hi) / 2:
      • PushBack happens without array resize:
        • Cost(i) = 1
        • Φ3(hi) = capacity (hi) / 2 − size(hi) = C/2 - k
        • Φ3(hi-1) = capacity (hi-1) / 2 − size(hi-1) = C/2 - (k-1)
        • Amortized Cost = 1 + C/2 - k - C/2 + k - 1 = 0
        • Amortized Cost = +0
      • PopBack happens without array resize:
        • Φ3(hi) = capacity (hi) / 2 − size(hi) = C/2 - k
        • Φ3(hi-1) = capacity (hi-1) / 2 − size(hi-1) = C/2 - (k+1)
        • Amortized Cost = 1 + C/2 - k - C/2 + k - 1 = 2
        • Amortized Cost = +2
    • When Size(hi) = Capacity(hi) / 2:
      • PopBack happened with array resize:
        • size(hi) = k => Capacity(hi) = 2×k; size(hi-1) = k + 1; Capacity(hi-1) = 4×k
        • Cost(i) = k
        • Φ3(hi) = max(2×size(hi)−capacity(hi),capacity(hi)/2−size(hi))
          = max(2×k−2×k,2×k/2−k) = 0
        • Φ3(hi-1) = max(2×size(hi-1)−capacity(hi-1),capacity(hi-1)/2−size(hi-1))
          = max(2×(k+1) - 4×k, 4×k/2 - (k+1)) = max(2 - 2×k, k - 1) = k - 1
        • Amortized Cost = k + 0 - (k - 1) = 1
        • Amortized Cost = +1
    • When Size(hi) > Capacity(hi) / 2:
      • PushBack without array resize:
        • size(hi) = k => Capacity(hi) = C; size(hi-1) = k - 1; Capacity(hi-1) = C
        • Cost(i) = 1
        • Φ3(hi) = 2×k - C
        • Φ3(hi-1) = 2×(k-1) - C
        • Amortized Cost = 1 + 2×k - C - (2×k - 2 - C) = +3
        • Amortized Cost = +3
      • PushBack with array resize:
        • size(hi-1) = k => Capacity(hi-1) = k; size(hi) = k + 1; Capacity(hi) = 2×k;
        • Cost(i) = k + 1
        • Φ3(hi) = 2×(k+1) - 2×k = 2
        • Φ3(hi-1) = 2×k - k = k
        • Amortized Cost = k + 1 + 2 - k = +3
        • Amortized Cost = +3
  • Therefore Φ3 does show that the amortized cost is O(1)

---

• Φ4 is a valid potential function but it's not the right answer:
  • Φ4(h0) = max(0, 2 × 0 − 0) = 0
  • Φ4(hi) ≥ 0 for all hi
  • Amortized Cost = Cost(i) + Φ3(hi) - Φ3(hi-1)
    • Let's take PopBack operation with resize:
      - size(hi) = k => Capacity(hi) = 2×k; size(hi-1) = k + 1; Capacity(hi-1) = 4×k
      - Cost(i) = k
      - Φ3(hi) = max(0, 2×size(hi)−capacity(hi)) = max(0, 2×k−2×k) = 0
      - Φ3(hi-1) = max(0, 2×size(hi-1)−capacity(hi-1)) = max(0, 2×(k+1) - 4×k) = max(0, 2 - 2×k) = 0
      - Amortized Cost = k + 0 - 0 = k
      - Amortized Cost = +k
  • Therefore Φ4 doesn't show that the amortized cost is O(1)

---