Dynamic Arrays: How append Stays Cheap

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.

1. Keep a block with some capacity (say, room for 8 items) even if the length (items actually stored) is smaller.
2. append while length < capacity: drop the item in the next free slot. O(1).
3. append when 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.

Counting the copies for 1,000 appends

A simulation of 1,000 appends under capacity doubling, tallying the total copy work.

capacity, length, copies = 1, 0, 0

for item in range(1, 1001):
    if length == capacity:
        copies += length
        capacity *= 2
    length += 1

print("appends:", length)
print("final capacity:", capacity)
print("total items copied:", copies)
print("copies per append:", copies / length)

Output

appends: 1000
final capacity: 1024
total items copied: 1023
copies per append: 1.023

The loop tracks three numbers: capacity is the room available, length is the items actually stored, and copies accumulates the work. The growth branch runs only when length == capacity, which happens at 1, 2, 4, 8, and so on, so it becomes rarer and rarer as the array gets bigger.

The total comes to 1,023 copies across 1,000 appends, close to one copy per append rather than n copies per append. That result is the whole reason list.append feels free in Python, and the next block gives it a name.

Amortized O(1)

A thousand appends cost only 1,023 copies in total, roughly one extra copy per append.

Spreading a rare expensive operation across the many cheap ones around it is called amortized analysis. So 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.

The doubling is what makes the arithmetic work. The copies form the sum 1 + 2 + 4 + ... + n⁄2, and such a sum is always less than n. Check it with small numbers: 1 + 2 + 4 + 8 = 15, which is less than 16. Total work for n appends therefore stays O(n), so each append averages O(1).

A tempting alternative is growing capacity by exactly 1 each time, which wastes no space at all and sounds tidier. The next section measures what that tidiness costs.

Doubling against growing by one

The two strategies side by side, differing in a single line.

def copies_doubling(n):
    capacity, length, copies = 1, 0, 0
    for _ in range(n):
        if length == capacity:
            copies += length
            capacity *= 2
        length += 1
    return copies

def copies_grow_by_one(n):
    capacity, length, copies = 1, 0, 0
    for _ in range(n):
        if length == capacity:
            copies += length
            capacity += 1
        length += 1
    return copies

for n in [100, 1000, 10000]:
    print(n, copies_doubling(n), copies_grow_by_one(n))

Output

100 127 4950
1000 1023 499500
10000 16383 49995000

The only difference is capacity *= 2 against capacity += 1, and the totals are not close.

Doubling stays near n because each growth step buys exponentially more room, so the next growth is twice as far away. Growing by one leaves the array full again immediately, so every append after the first finds no free slot and pays a full copy.

Those grow-by-one totals are 0 + 1 + 2 + ... + (n−1) = n(n−1)⁄2, the triangle sum from lesson 1-2, which is O(n²) rather than O(n). At n = 10,000 that is 50 million copies against 16,000.

Zero wasted space costs quadratic time, and that trade is why every real dynamic array multiplies its capacity instead of adding to it.

Calling list.append amortized O(1) adds the claim that appends are O(1) on average across many calls, even though a rare one pays an O(n) copy.

The distinction matters because the plain claim would be false. One append in a while does land on a full array and does copy every existing item.

Doubling makes those events exponentially rare, so the total work for n appends is O(n), which averages out to O(1) each. Amortized means averaged over the sequence with the rare spikes included, rather than measured on the best case.

The practical consequence is worth knowing. If your program cannot tolerate an occasional pause, amortized O(1) is not the same guarantee as O(1), which is why real-time systems sometimes preallocate capacity to avoid the spike entirely.

Appending twice to a dynamic array of length 8 and capacity 8 costs an O(n) copy and then nothing.

The first append finds the array full, so it allocates a block of roughly double the capacity, 16, copies the 8 existing items across, and places the new one. The second append finds 7 free slots waiting and is a pure O(1) drop-in. Final length is 10.

Only the append that lands on a full array pays anything unusual, which is exactly the pattern the amortized average is built on. Seven of the next eight appends will be free.

One footnote on accuracy. CPython's real growth factor is a little under 2, closer to 1.125 for large lists plus a constant, but doubling is the right mental model and gives the same asymptotic result.