Amortized Cost of a Dynamic Array

Problem

You are implementing a growable array on top of fixed-size blocks of memory. When the array is full and another element is appended, you must allocate a new block, copy every existing element into it, and free the old one.

Three growth policies are on the table:

• Doubling: new capacity = 2 × old capacity.
• Factor 1.5: new capacity = ⌈1.5 × old capacity⌉.
• Additive: new capacity = old capacity + 16.

For each policy, derive the total number of element copies performed over n appends starting from an empty array, and hence the amortized cost per append. Then implement the array with a configurable growth policy and a counter that records every element copy, so the derivation can be checked empirically.

• Copying one element costs 1. Allocation and freeing cost nothing for this analysis.
• Start with capacity 1 under every policy.

Examples

• Doubling, n = 8 appends from capacity 1: resizes happen when going to sizes 2, 3, 5 (capacities 1 → 2 → 4 → 8), copying 1 + 2 + 4 = 7 elements in total. Seven copies for eight appends: under one copy per append on average.
• Doubling, n = 1,000,000: total copies = 1 + 2 + 4 + ... + 524,288 = 1,048,575, just over n and always under 2n. Amortized cost ≈ 1 copy plus the write itself.
• Additive by 16 from capacity 1, n = 1,000,000: a resize every 16 appends, copying 1, 17, 33, ... elements over about 62,500 resizes. Total ≈ 16 × (1 + 2 + ... + 62,500) ≈ 31 billion copies. Amortized cost ≈ n / 32 ≈ 31,000 copies per append, which is Θ(n).

Hints

1. Write down the sizes of the arrays that get copied. Under doubling they form a geometric series; what does that sum to?
2. Under additive growth the copied sizes form an arithmetic series. What does that sum to?
3. For the accounting view: charge each append 3 units. One pays for the write. Where do the other two go, and why is the bank never negative at a resize?