Appending Is O(1) on Average, and the Average Hides the Interesting Part
Appending to a list is described as constant time, and the word usually left off is amortised. It matters, because individual appends are not constant time at all. Most write one slot and stop. Occasionally one has to allocate a bigger block of memory and copy every element into it, and that append costs the entire current length.
The average stays flat only because the expensive appends get rarer at exactly the rate they get more expensive. That is a statement about a distribution, and squashing it into one letter throws away the only interesting part.
Watch the spikes
The lower row is one bar per append. Flat means a single slot was written; a spike is a reallocation copying everything.
A dynamic array is a fixed block of memory with spare room on the end. Appending usually writes one slot and stops. When the spare room runs out, a larger block has to be allocated and every existing element copied into it — so that one append costs the entire current length, and the appends after it are cheap again.
How much larger the new block should be is the decision that matters, and it is not a tuning detail. Over 1,000 appends, growing by one slot at a time copies 499,500 elements — 499.50 per append — because reallocations never get rarer while the amount copied keeps rising. Doubling copies 1,023 in total, 1.02 per append, and the figure stays near 1 however large the array gets. Growing by a fixed AMOUNT is quadratic no matter how big the amount is; growing by a FACTOR is linear.
Pick a growth strategy and append. The lower row is one bar per append, so a flat stretch is a run of single-slot writes and a spike is a reallocation copying everything.
- Elements held
- 0
- Capacity
- 0
- Elements copied
- 0
- Copies per append
- 0.00
The same run, as text
Strategy
Spare room
Expensive appends
Start with 'multiply by 2', append twenty or so, then switch to 'grow by 1' and do it again. The bar row tells two completely different stories.
With doubling, the spikes get taller and further apart together — that is amortisation happening in front of you. With grow by 1, every single append is a spike, because the array is always exactly full.
Growing by a bigger chunk does not fix it
The intuitive repair for “grow by 1” is to grow by more — 8 slots, or 1000. It helps by a constant factor and changes nothing that matters.
import math
def total_copies(n, strategy):
"""Elements copied while appending n items. A reallocation copies everything held so far."""
length, capacity, copied, reallocations = 0, 0, 0, 0
for _ in range(n):
if length == capacity:
kind, amount = strategy
capacity = capacity + amount if kind == "add" else max(1, math.ceil(capacity * amount))
copied += length # every existing element moves to the new block
reallocations += 1
length += 1
return copied, reallocations
STRATEGIES = [("grow by 1", ("add", 1)),
("grow by 8", ("add", 8)),
("multiply by 1.5", ("mul", 1.5)),
("multiply by 2", ("mul", 2))]
print(f"{'strategy':<16} {'appends':>8} {'copies':>12} {'reallocs':>9} {'copies per append':>18}")
for n in (16, 1_000, 100_000):
for name, strategy in STRATEGIES:
copied, reallocs = total_copies(n, strategy)
print(f"{name:<16} {n:>8,} {copied:>12,} {reallocs:>9} {copied / n:>18.2f}")
print()strategy appends copies reallocs copies per append grow by 1 16 120 16 7.50 grow by 8 16 8 2 0.50 multiply by 1.5 16 31 7 1.94 multiply by 2 16 15 5 0.94 grow by 1 1,000 499,500 1000 499.50 grow by 8 1,000 62,000 125 62.00 multiply by 1.5 1,000 2,120 17 2.12 multiply by 2 1,000 1,023 11 1.02 grow by 1 100,000 4,999,950,000 100000 49999.50 grow by 8 100,000 624,950,000 12500 6249.50 multiply by 1.5 100,000 276,492 29 2.76 multiply by 2 100,000 131,071 18 1.31
The right column is the whole argument. Read it down each strategy as n grows:
- grow by 1: 7.50, then 499.50, then 49,999.50. It tracks
n. - grow by 8: 0.50, then 62.00, then 6,249.50. Eight times better, and still tracking
n. - multiply by 2: 0.94, then 1.02, then 1.31. It stays put.
“Grow by 8” looks excellent at sixteen appends — the best row in the first block, in fact — and is catastrophic at a hundred thousand. A constant improvement to a quadratic algorithm is still quadratic, and small-input benchmarks are exactly where that hides.
Notice the reallocation counts too. Doubling reallocates 18 times while appending 100,000 elements. Growing by 1 reallocates 100,000 times.
Why multiplying works
Because the work done between reallocations grows in step with the work each reallocation costs. Double from 1024 to 2048 and you copy 1024 elements — but you have also bought 1024 free appends before the next reallocation. Every element copied is paid for by roughly one cheap append that follows it, so the cost per append stays bounded no matter how large the array becomes.
Growing by a fixed amount breaks that balance. The free appends you buy stay at 8 forever while the copy cost keeps climbing, so the ratio between them worsens without limit.
The choice of factor is a memory-versus-copying trade rather than a correctness one. Doubling can leave up to half the block unused right after a growth; 1.5 wastes less and copies more. Real implementations differ, and both are linear overall.
What this page simplifies
- Copies, not seconds. Element moves are counted. A real reallocation may also be able to extend a block in place and copy nothing, and copying contiguous memory is far faster per element than these counts suggest.
- Nothing shrinks. Removing elements does not release capacity here. Real implementations usually shrink only well below half full, precisely to avoid thrashing at the boundary.
- No allocator behaviour. Where the new block comes from, and whether allocation itself is cheap, is a whole layer this model ignores.
- Appending only. Inserting at the front shifts every element on every call, growth or no growth, and no growth strategy rescues it.