Arrays, Dynamic Arrays and Hash Tables: Where O(1) Comes From and What It Costs

Contiguity is the whole argument

An array stores \(n\) elements in one block. Element \(i\) lives at base + i * width, so indexing is arithmetic — \(\Theta(1)\) worst case, no traversal. A linked list stores each element with a pointer to the next, anywhere in memory.

The textbook comparison says the list wins on insertion. In practice it usually does not, for a reason big-O cannot see: hardware moves memory in cache lines (64 bytes on x86-64), so scanning an array fetches many elements per miss. Chasing pointers pays a fresh, unpredictable miss per node. And the list’s celebrated \(\Theta(1)\) insertion assumes you already have the node; finding it costs \(\Theta(n)\) first.

Lists still earn their place when you hold interior positions and splice often — an LRU cache pairing a hash table with a doubly linked list is the standard example.

Why appending is amortised O(1)

A dynamic array keeps spare capacity. When it fills, allocate a bigger block, copy everything, free the old one. That copy is \(\Theta(n)\), so how is append \(O(1)\)?

Grow by a constant factor. Doubling from capacity 1, resizes happen at sizes \(1, 2, 4, \dots, 2^k \le n\), and the total number of elements ever copied over \(n\) appends is

So \(n\) appends cost less than \(3n\) elementary operations in total — \(O(n)\) for the whole sequence, hence \(O(1)\) amortised per append. Any growth factor \(c>1\) works: the copies sum to \(\tfrac{c}{c-1}n\). CPython over-allocates by roughly one-eighth, \(c \approx 1.125\), giving about \(9n\) copies in total — still linear, and it wastes far less memory than doubling.

Additive growth does not work: growing by a fixed 10 slots gives resizes at \(10, 20, 30, \dots\) and copies summing to \(\Theta(n^2/10)\). The geometric factor is load-bearing.

Note what amortised does not say: nothing about an individual append, one of which copies the whole array — the worst-versus-amortised distinction exactly.

Hash tables

A hash table stores key–value pairs in \(m\) slots, placing key \(k\) at index \(h(k) \bmod m\) for a hash function \(h\). If \(h\) scattered keys perfectly and no two collided, lookup would be one array index. Two keys will collide — with \(n\) keys in \(m\) slots and \(n>m\) it is forced, and long before that the birthday bound makes it near-certain — so the design is entirely about collision handling and about the load factor \(\alpha = n/m\).

Chaining puts colliding keys in a per-slot linked list (or small array). Under the simple uniform hashing assumption, an unsuccessful search examines \(1 + \alpha\) slots on average, so as long as \(\alpha\) is held below a constant by resizing, lookup is \(\Theta(1)\) expected. It degrades gracefully and tolerates \(\alpha > 1\).

Open addressing stores everything in the table itself: on collision, probe a deterministic sequence of alternative slots. It needs \(\alpha < 1\) and is more cache-friendly, since probes stay inside one array. Under uniform hashing the expected number of probes for an unsuccessful search is at most \(1/(1-\alpha)\):

That table is the whole design argument: cost is flat until \(\alpha\) approaches 1, then explodes. Implementations therefore resize at a fixed threshold — and deletion cannot simply blank a slot, because that would break probe chains; it writes a tombstone instead.

Worst case is \(\Theta(n)\) either way. If every key hashes to the same slot, lookup is a linear scan. Not hypothetical: it was a real denial-of-service vector against web frameworks, where an attacker sent form fields chosen to collide.

What Python actually gives you

dict and set are open-addressed tables. Since 3.6 dict keeps a compact array of entries in insertion order with a separate index array — order preservation became a language guarantee in 3.7 — and it resizes when the used entries exceed two-thirds of the allocated slots. Since 3.3, string and bytes hashing is randomised per process with a seed (SipHash, PEP 456), which is why iteration order of a set of strings can change between runs and why the collision attack is defused.

Three practical consequences:

xs = list(range(1_000_000))
9_999 in xs                 # Theta(n) scan of a list

seen = set(xs)
9_999 in seen               # Theta(1) expected

# keys must be hashable: hashable roughly means immutable
d = {}
d[(1, 2)] = "ok"            # tuple of hashables: fine
try:
    d[[1, 2]] = "boom"      # list is mutable and unhashable
except TypeError as e:
    print(e)                # unhashable type: 'list'

# the canonical use: turn a nested loop into one pass
def two_sum(nums, target):
    """Indices of the first pair summing to target. Theta(n) expected."""
    seen_at = {}
    for i, x in enumerate(nums):
        if target - x in seen_at:
            return seen_at[target - x], i
        seen_at[x] = i
    return None

print(two_sum([2, 7, 11, 15], 26))   # (2, 3), since 11 + 15 = 26

Membership in a list is \(\Theta(n)\) and in a set is \(\Theta(1)\) expected — this single substitution fixes more accidentally quadratic ML data pipelines than any other change.

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, 4th ed. MIT Press, 2022 — ch. 11 for hashing, ch. 16 for amortised analysis.
2. Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., §6.4. Addison-Wesley, 1998.
3. CPython source. Objects/listobject.c (over-allocation in list_resize) and Objects/dictobject.c.
4. Python Software Foundation. PEP 456 — Secure and Interchangeable Hash Algorithm.
5. Python Software Foundation. TimeComplexity — Python Wiki.
6. Aumasson, J.-P., & Bernstein, D. J. SipHash: A Fast Short-Input PRF. INDOCRYPT 2012.