Suppose a program reads an unknown number of values and must later retrieve the value at any specified position. An array gives direct access to position , but a fixed array cannot promise space for an unknown future input. Allocating an enormous array in advance wastes memory and still imposes a limit. A dynamic array keeps the direct-access representation while replacing its backing storage when necessary.
Replacement can be expensive: existing values must be copied. The interesting question is therefore about a sequence of operations. Can we arrange the expensive replacements so that the total cost of many appends is linear? The answer depends on the growth rule. If deletions also reclaim storage, their threshold matters just as much.
Keep the sequence separate from its storage
Definition 11.1.1
(Size, capacity and the represented sequence)
A dynamic array stores a backing array , a size , and a capacity , with
Its abstract sequence consists exactly of . The remaining slots are spare storage, not additional sequence entries. An index is valid precisely when .
append(x) adds at the end. pop() removes and returns the last entry, and requires a nonempty sequence. Reading or replacing an existing entry by index preserves the size and capacity.
We begin with an empty sequence and capacity 1. If an append finds , write the new value at and increment . If , allocate capacity , copy the live values in order, replace the backing storage, and then append. Doubling is an implementation rule; it does not change the sequence operations seen by the caller.
The copying step must preserve order. After copying, the old entry at index is still at index , so every existing indexed query has the same answer. The new value becomes entry , and the new size is . Storage movement changes the representation, while append changes the abstract sequence in the specified way.
Choose a cost model before counting
For the analysis below, charge one unit for the constant ordinary work of each append or pop, plus one unit for every live entry copied during resizing. Thus
This is an explicit algorithmic cost model, not an exact count of machine instructions. Comparisons and metadata updates take constant time. The model does not charge for initializing unused slots in a new allocation. If allocation initializes all slots in linear time, the asymptotic bounds below remain valid: each resize's new capacity is within a constant factor of the live entries it copies, apart from constant-size boundary cases. The precise constants in the tables refer to the stated model.
Worked example 11.1.2
(The ninth append is expensive, but the first nine are linear in total)
Start with size 0 and capacity 1. Append the values 1 through 9.
| Appended value | Size afterwards | Capacity afterwards | Entries copied | Operation cost |
|---|---|---|---|---|
The total is nine ordinary units plus copied entries, giving cost 24. The ninth append alone costs 9. Calling append amortized constant-time therefore cannot mean that every individual call has constant worst-case cost.
Sum a whole sequence of appends
Proposition 11.1.3
(Linear total cost of doubling)
Start from the empty dynamic array with capacity and use the doubling rule, with no pops. In the cost model above, every sequence of appends has total cost less than .
Proof
(Geometric copies have a linear sum)
Consider appends from the initial empty array. If resizing occurs, the numbers of entries copied are
where : copying entries happens when inserting entry . The total copying cost is
Add the ordinary units. The total cost is less than . If no resize occurs, the same bound holds immediately. This deterministic bound applies to every append sequence of length , regardless of the values stored.
An amortized bound limits the total cost of a sequence by assigning a bounded average charge per operation. A costly append can be paid for by the many cheaper appends surrounding it.
Concept lensAlgorithmic
Tokens on entries
Charge every append 3 units: one pays for the write and two stay on the new entry. A full array of capacity holds units on the entries written since it was allocated, exactly the cost of copying entries; for the entry holds 2 units. No balance goes negative, so appends cost at most .
Common mistake
(Amortized cost is not average-case cost)
Reading amortized constant as constant on average over random inputs is wrong. The bound holds for every append sequence of length , with no probability involved; what is averaged is the cost over the operations of one fixed sequence. Conversely, the bound does not make each call cheap: the ninth append in the table above costs 9.
The doubling rule also bounds unused capacity. With append only and , we have : immediately after growth the new capacity is twice the old size, while the new size is one larger than the old size. Between growth events the capacity stays fixed and the size increases.
Counterexample mode
Adding one slot at a time loses the linear total bound
Suppose a full array grows from capacity to . Starting at capacity 1, appends 2 through copy entries. Their sum is
so total append cost is and amortized cost is . Every array still satisfies , and every indexed query is correct. The functional invariant is preserved, but the growth policy fails the performance goal. A fixed-size capacity increment has the same asymptotic problem.
For a fixed integer growth factor , the copy sum is instead . Larger factors leave more spare storage after growth. This is a space-and-copying tradeoff, not a reason to allocate without limit.
Shrinking needs a gap between thresholds
If the array never shrinks, popping almost every value can leave a very large allocation holding very few entries. A natural first attempt is to halve capacity as soon as the size falls to half the capacity. Combined with doubling when full, this policy can repeatedly undo its own work.
Counterexample mode
Half-full shrinking can alternate with immediate regrowth
Start with a full array of size and capacity . Append once: it copies entries, becomes size , and has capacity . Pop once: the size returns to , exactly half the capacity. The proposed shrinking rule copies entries back into capacity .
The same append-pop pair can now repeat. Each pair copies entries despite making no lasting change to the size. This is not merely an unfair choice of a costly initial state: first build the full array using appends, then repeat the pair times. The resulting updates make at least copies. The total cost is quadratic in the sequence length.
Instead, keep the growth rule and shrink after a pop only when the new size satisfies , with capacity greater than 1. Halve the capacity, but never below 1. Because capacities are powers of two, use n <= C // 4 in code. After a usual shrink, occupancy returns to one half, leaving room both for more appends and for more pops before another resize.
This gap between the full and quarter-full thresholds is often called hysteresis. Its mathematical purpose is to force enough operations between costly changes. Saying that the gap “usually helps” is weaker than proving a bound for every mixed sequence; the next argument supplies that proof.
A potential accounts for both growth and shrinkage
Assign each state a nonnegative potential
It is zero at half occupancy. It grows toward either a full or an almost empty array, storing credit for the corresponding future resize. The initial state has potential .
Proposition 11.1.4
(Constant amortized cost with the quarter-full rule)
Start from the empty dynamic array with capacity . An append that finds the array full doubles the capacity. After each pop, the capacity is halved exactly when it exceeds and the new size is at most . Then every sequence of valid appends and pops has total actual cost at most .
Proof
(A potential for mixed appends and pops)
For an operation from state to , define its amortized charge by
For capacities at least 4, the cases below give every resize and the ordinary operations. At the midpoint, the potential is zero, so crossing the midpoint obeys the same stated bounds.
| Operation | Actual cost | Potential change | Amortized charge |
|---|---|---|---|
| Append without growth, in upper half | |||
| Append without growth, in lower half | |||
| Append at full capacity | |||
| Pop without shrink, staying in upper half | |||
| Pop without shrink, entering or in lower half | |||
| Pop and shrink from capacity |
For growth, the old potential is . The new size is and the new capacity is , so the new potential is 2. This releases enough credit to pay for copying the old entries.
For shrinking with , the first eligible size after the pop is . Just before that pop the size was : after every previous operation the array was above the shrinking threshold. The old potential is . After shrinking, capacity is , occupancy is one half, and potential is zero. The operation copies live entries, giving charge 2.
Capacities 1 and 2 have only a constant number of boundary states. Direct substitution gives append charge at most 3 and pop charge at most 2 there as well. In particular, popping the last entry from capacity 2 shrinks to capacity 1 and has charge .
For updates, the potential differences telescope:
because . Thus every valid mixed sequence of appends and pops has constant amortized update cost under this policy.
Proof X-ray
Why the gap between the two thresholds pays for shrinking
The potential has two slopes. On the upper half it rises by per append, so the appends between half occupancy and a full array store the units needed to copy entries. On the lower half it rises by per pop, so the pops between half occupancy and the shrink threshold store the units needed for that copy.
The proof rests on one property of the policy: after every operation the size exceeds (unless ). That is why a shrinking pop starts from size , where the stored potential is . The charge added to it pays for the actual cost , and the shrink leaves the array exactly half full with zero potential, so the next resize is far away in both directions.
Without the gap the argument collapses. If shrinking were triggered at half occupancy, the pop in the previous counterexample would move from , with potential , to , with potential , at actual cost . The amortized charge would be , which no constant bounds.
A negative amortized charge, such as in one table row, is allowed. It records a release of previously stored potential. The actual operation still costs a positive amount. Potential is an analysis device; the implementation does not store or spend a balance of tokens.
Worked example 11.1.5
(A five-unit pop can have amortized charge two)
Reach size 9 and capacity 16 by the earlier append sequence, then pop four times to reach size 5 without shrinking. At state the potential is .
One more pop gives size 4 and triggers shrinking to capacity 8. It copies four live entries, so actual cost is 5. The new state has potential zero. Its amortized charge is therefore .
The four copied entries retain their indices and order. The removed fifth value is not copied. Shrinking changes spare storage, not the surviving abstract sequence.
Worked example 11.1.6
(A mixed sequence through the smallest capacities)
Start at with . Append , , , then pop three times, always under the quarter-full rule.
| Operation | State afterwards | Actual cost | Potential | Amortized charge |
|---|---|---|---|---|
| append | ||||
| append (full: copy 1) | ||||
| append (full: copy 2) | ||||
| pop (, no shrink) | ||||
| pop (: shrink, copy 1) | ||||
| pop (: shrink, copy 0) |
The actual costs add up to . The charges add up to as well, because the sequence ends in the state where it began, so and the telescoping identity gives equality. The last pop is the boundary case: it empties the sequence and shrinks capacity 2 to capacity 1 without copying anything. A further pop on this empty array raises IndexError and changes neither the size nor the capacity.
After every operation, if this policy also gives ; otherwise a shrink would already have been triggered. Following a shrink, in the usual nonempty case. The empty state has capacity 1. Thus storage remains . During resizing the old and new allocations coexist temporarily, but their combined capacity is still within a constant factor of .
A small implementation makes the policy explicit
The following Python class uses a fixed-length list as its backing storage and performs the resizing itself. copied counts live relocations; work counts the cost model above. These counters explain the algorithm rather than measure allocator or interpreter runtime. Indexing checks use size, not capacity. The private resize method is called only with enough capacity for all live entries.
class DynamicArray:
def __init__(self):
self.data = [None]
self.size = 0
self.copied = 0
self.work = 0
@property
def capacity(self):
return len(self.data)
def _resize(self, capacity):
replacement = [None] * capacity
for i in range(self.size):
replacement[i] = self.data[i]
self.copied += self.size
self.work += self.size
self.data = replacement
def append(self, value):
if self.size == self.capacity:
self._resize(2 * self.capacity)
self.data[self.size] = value
self.size += 1
self.work += 1
def pop(self):
if self.size == 0:
raise IndexError("pop from empty dynamic array")
self.size -= 1
value = self.data[self.size]
self.data[self.size] = None
self.work += 1
if self.capacity > 1 and self.size <= self.capacity // 4:
self._resize(self.capacity // 2)
return value
def __getitem__(self, index):
if not 0 <= index < self.size:
raise IndexError("index outside sequence")
return self.data[index]
def __setitem__(self, index, value):
if not 0 <= index < self.size:
raise IndexError("index outside sequence")
self.data[index] = value
Indexed reading and replacement take worst-case time in this model. Append and pop take amortized time, but a resizing call can cost . Inserting at the front of an array still requires shifting all later entries; the resizing proof does not make that operation constant-time. Keep the operation, cost model and kind of bound together when comparing data structures.
Common mistake
(Capacity is not the length)
In the Python class, len(self.data) is the capacity. With size 5 and capacity 8 it returns 8, and the three spare slots hold None values that are not sequence entries. Using it to test indices would accept index 6 and read a spare slot. The size field must define validity.
Exercises and worked solutions
Quick check
(1. Compare a sequence total with one operation)
What are the total costs after eight and after nine appends from the initial state? Why do these numbers support an amortized bound without proving a constant worst-case bound for each append?
Solution · Solution 1
Eight appends cost . Nine cost . The ninth call alone costs . Both totals are below three times the number of calls, but the cost of the last call grows with the previous full capacity.
Quick check
(2. Compare two growth rules exactly)
Starting with capacity 1, append six values. Compute the copied-entry count and total cost if capacity increases by one each time, and if it doubles.
Solution · Solution 2
Incrementing capacity copies entries and costs . Doubling copies entries and costs . These are counts under the stated model, not timings of a particular programming language.
Quick check
(3. Spare storage is not part of the sequence)
An array has size 5 and capacity 8. Is index 6 valid? Does replacing entry 2 change either the size or capacity? Explain using the abstraction invariant.
Solution · Solution 3
Index 6 is invalid because valid indices are 0 through 4. The spare slot exists physically but represents no sequence entry. Replacing entry 2 changes one existing value while keeping size 5 and capacity 8. Validity depends on size, not the allocated slot count.
Quick check
(4. Compute a shrinking operation's potential charge)
At size 5 and capacity 16, perform one pop under the quarter-full rule. Give the new size, capacity, copy count, actual cost, both potentials and amortized charge.
Solution · Solution 4
The new size is 4, triggering capacity 8. Four surviving values are copied; actual cost is 5. Potential changes from to , so the amortized charge is .
Quick check
(5. Diagnose the half-full shrinking policy)
Start full at size and capacity 8. Under doubling and half-full shrinking, what happens in one append-pop pair? Why can repeating the pair invalidate constant amortized cost even when the setup operations are included?
Solution · Solution 5
Append copies eight values into capacity 16; pop returns to size 8 and copies eight values back into capacity 8. The pair costs and restores the same size and capacity. In the general construction, building capacity takes appends, then pairs make copies in only updates altogether. Including setup therefore does not rescue a linear total bound.
Quick check
(6. Change the growth factor without confusing the tradeoff)
For ten appends, compare doubling with tripling, both starting at capacity 1 and without deletions. Give final capacity and copied-entry count. What additional cost remains if you instead insert each new value at the front?
Solution · Solution 6
Doubling ends at capacity 16 and copies entries. Tripling ends at capacity 27 and copies entries. The latter uses more spare storage at this point. Front insertion additionally shifts all existing entries on every call, giving shifts for ten calls and shifts for calls. Geometric resizing does not remove those shifts.