A dynamic array doubles when full and halves when it drops to 1/4 full. Using the potential method, exhibit a potential function and show that push and pop are both O(1) amortised. Why does halving at 1/2 full break the bound?

A dynamic array doubles when full and halves when it drops to 1/4 full. Using the potential method, exhibit a potential function and show that push and pop are both O(1) amortised. Why does halving at 1/2 full break the bound?

Approach: Define a potential that is zero right after a resize and grows to pay for the next one, then compute amortised cost as actual cost plus the change in potential in each of the four cases.

The potential method works with Phi = 2n - m when n >= m/2 and Phi = m/2 - n otherwise, where n is the size and m the capacity. Both branches are zero just after a resize and non-negative always, so the total amortised cost upper bounds the total actual cost. A push with no resize costs 1 and raises Phi by 2, so the amortised cost is 3. A push that doubles costs m + 1 actual work while Phi falls from m to 2, so the amortised cost is m + 1 + 2 - m = 3. The pop cases are symmetric and also bounded by 3. Halving at 1/2 full removes the hysteresis: at exactly the boundary an alternating push, pop, push, pop sequence forces a grow then a shrink then a grow, each costing Theta(m), so k operations cost Theta(km) and the amortised bound becomes linear. The gap between the grow threshold and the shrink threshold is what guarantees Omega(m) cheap operations between any two resizes.

Follow-up: What growth factor minimises total memory copied while keeping amortised O(1), and what is the trade against peak memory?

Key concepts: potential method, amortised cost, hysteresis, resize threshold.