Dynamic Arrays and Amortized Analysis

Build the mental model

A raw fixed-size array can't grow — once it's full, there's no room for a new element in the next memory slot, because something else might already occupy it. Python's list solves this by being a dynamic array: internally it doesn't allocate exactly n slots for n elements, it over-allocates extra capacity, so most `.append()` calls just write into an already-reserved slot and increment a length counter — that's O(1). Only when the reserved capacity runs out does Python allocate a new, larger block (typically growing by roughly 1.125x to 2x depending on size) and copy every existing element into it, which costs O(n) for that one call. If resizes happened constantly this would be no better than a naive array, but because each resize roughly doubles capacity, resizes become exponentially rarer as the list grows — across n total appends, the expensive O(n) resizes happen only O(log n) times and their total cost still sums to O(n). Averaged, or 'amortized', across all n appends, that's O(1) per append on average, even though any single append can occasionally be the expensive one that triggers a resize.

Connect it to a real scenario

When the Tutorial Platform rebuilds its search index — appending an entry for every lesson in the catalog one at a time — amortized O(1) append is exactly why that build stays fast: even with tens of thousands of lessons, Python's list handles the occasional resize so efficiently that the total build time still scales linearly with lesson count, not quadratically. If lists resized on every single append instead, indexing the whole platform would become dramatically slower as the catalog grows, which is the kind of hidden cost this lesson's mental model helps you catch before it ships.

• Python's list over-allocates capacity, so most .append() calls are O(1) writes into reserved space
• A resize (copying all elements into a bigger block) costs O(n) but happens only O(log n) times over n appends
• Averaged across all appends, this makes .append() 'amortized O(1)' even though individual calls vary

Try the working example

import time

# Appending n items to a list -- each individual call is amortized O(1),
# so the total time to build the list grows linearly with n, not quadratically.
n = 200_000
data = []
start = time.perf_counter()
for i in range(n):
    data.append(i)  # usually O(1); occasionally O(n) when the list resizes
elapsed = time.perf_counter() - start

print(f'Appended {n} items in {elapsed:.4f} seconds')
print('List length:', len(data))

Prints the elapsed time to append 200,000 items (a small fraction of a second) and confirms the final length is 200000, showing the occasional O(n) resizes don't make total append time blow up.

Python Docs — Data Structures — Data Structures & Algorithms