The fixed-size problem
A raw array has a catch: it is one contiguous block, so its size is fixed when it is created. The memory right after it may already belong to something else, so you cannot just extend it.
Python's list feels infinitely growable because it is a dynamic array: an ordinary array plus a growth strategy.
- Keep a block with some capacity (say, room for 8 items) even if the length (items actually stored) is smaller.
appendwhile length < capacity: drop the item in the next free slot. O(1).appendwhen full: allocate a new block about twice as big, copy every item over, then append.
Step 3 is expensive, an O(n) copy. The trick is how rarely it happens. Let's count.
Code exercise · python
Run this simulation of 1,000 appends with capacity doubling. Count the total copy work: it comes out close to 1 copy per append, not n copies per append.
Amortized O(1)
1,000 appends cost only 1,023 copies total, roughly one extra copy per append. Spreading a rare expensive operation across the many cheap ones that surround it is called amortized analysis. We say list.append is amortized O(1): any single append might trigger an O(n) copy, but the average over a long run of appends is constant.
Why doubling? The copies form the sum 1 + 2 + 4 + ... + n⁄2, which is always less than n (try it: 1 + 2 + 4 + 8 = 15 < 16). Total work for n appends stays O(n), so each append averages O(1).
A tempting alternative is growing capacity by 1 each time, with no wasted space. Your turn to see why nobody does that.
Code exercise · python
Your turn. `copies_doubling` is done. Implement `copies_grow_by_one`: same simulation, but when full, copy `length` items and grow capacity by just 1 (`capacity += 1`). Compare the totals. Doubling stays near n. Grow-by-one is the triangle sum from lesson 1-2, O(n²).
Quiz
`list.append` is called amortized O(1). What does "amortized" add to the claim?
Quiz
A dynamic array has length 8 and capacity 8. You append two items. What happens?