Pay for resizing with amortized analysis

Prerequisites: Arrays, geometric sums, and the distinction between worst case and expectation.

Learning objectives

• Bound total copying under geometric growth.
• Construct a potential-function argument.
• Explain why a shrinking policy needs hysteresis.

An occasional expensive operation

An array stores elements in contiguous indexed slots. A dynamic array maintains a logical length n and capacity C. If an append finds n<C, it writes one slot. If the array is full, it allocates a larger region, copies the n existing elements, and writes the new one. That particular append costs Theta(n). Amortized analysis asks how much an entire sequence costs, without assigning probabilities to inputs.

Start with capacity 1 and double whenever full. In the first eight appends, copied-element counts are 0,1,2,0,4,0,0,0. There are eight ordinary writes and seven copies, totaling fifteen primitive moves in this simplified model. For N appends, capacities copied form a geometric series smaller than 2N. Total work is therefore less than 3N, giving constant amortized cost per append. Any chosen append can still pause for linear work.

A potential stores prepaid work

For states reached by append-only doubling after initialization, use potential Φ=2n−C, taking the initial empty allocation separately. A cheap append increases n by one without changing C, so potential rises by two. Its actual cost is one and amortized cost is three. At a resize from a full capacity C, the new length is C+1 and new capacity is 2C. Potential changes from C to 2, while actual cost is C+1. Adding the potential change again gives three.

The algebra formalizes the accounting story: cheap appends accumulate credit and the resize consumes it. Summing amortized costs telescopes the potential differences. A lower-bounded potential ensures that the proof has not secretly borrowed unlimited credit from the future. This is a deterministic bound over sequences, unlike an expected bound over random hash choices.

Shrinking can destroy the argument

Suppose an array halves its capacity as soon as it becomes half full and doubles as soon as it becomes full. A delete followed by an append near the threshold can repeatedly trigger large copies. A common remedy is to shrink at a lower occupancy threshold, such as one quarter, while growing at full occupancy. The gap is hysteresis: enough operations must occur before the next opposite resize.

Geometric growth trades memory slack against copying frequency. A growth factor close to one reduces unused capacity but increases the copying constant. Exact factors, minimum capacities, overflow checks, and allocation failures are implementation contracts. A real-time application may instead prefer segmented storage or incremental migration to bound individual pauses. Read the array-based-list analysis in Open Data Structures, and identify where its abstract costs omit your allocator and machine.

Practice problem

Simulate appending nine elements starting with capacity 1 and doubling when full. List capacities after every append, count ordinary writes and copied elements separately, and identify the worst individual append. Then contrast growth by one slot: derive its total copies for nine appends and for general N.

Worked solution

Capacities are 1,2,4,4,8,8,8,8,16. There are nine new-element writes and 1+2+4+8=15 copies, totaling 24 moves. The ninth append costs nine moves: eight copies plus the new write. Growing by one copies 1+2+…+8=36 elements for nine appends, plus nine writes. In general it copies N(N−1)/2 elements, which is quadratic. The doubling bound is about the total sequence, not a promise that every append is cheap. Allocation overhead and element move constructors are deliberately excluded from this model.

Check your understanding

An array is full with 8 entries and capacity 8. An append doubles capacity. With potential Φ=2n−C and unit cost per copy or write, what is its amortized cost?

• 9
• 3
• 17
• 1

Explanation

Actual work is 8 copies plus 1 write. Potential changes from 8 to 2, so amortized work is 9−6=3.

An array doubles when full and halves when deletion leaves it half full. Which repeated operation pattern can cause expensive resizing on every operation?

• Append forever without deleting.
• Alternate between n=C/2 and n=C/2+1 around a shrink/grow boundary.
• Delete every element and stop.
• Read the last element repeatedly.

Explanation

Shrinking to a full smaller array makes the next append grow it again; deletion can immediately shrink it back. A quarter-full shrink threshold introduces room between these boundaries.

Primary reading

• Open Data Structures: Pat Morin, open textbook

Open the study and save your work →