The number one cause of “it was fast in staging with 500 rows and times out in production with 50,000” is a container choice. The code is identical. Only n changed. And it is invisible in a flat profile at small n, because at small n it genuinely is fast.
The numbers
Measured on a 10-core arm64 machine, CPython 3.14.6:
| operation | list | deque / set | ratio |
|---|---|---|---|
| 100,000 × prepend |
insert(0, i) 1157 ms |
appendleft 1.04 ms |
~1,100x |
| 100,000 × pop from front |
pop(0) 570 ms |
popleft ~1 ms |
~500x |
| 10,000 membership tests in 10,000 items | 243 ms | 0.14 ms | ~1,700x |
Three-orders-of-magnitude differences are not micro-optimisation. They are the difference between a request and a timeout.
Why
A list is a contiguous array of pointers. Appending is amortised O(1) because the array over-allocates (article 11.12 shows the growth pattern). Inserting or removing at the front must move every remaining pointer — a memmove of 8 * n bytes — so it is O(n), and doing it n times is O(n²).
A collections.deque is a doubly-linked list of fixed-size blocks. Appending and popping at either end is O(1). Indexing in the middle is O(n), which is the trade.
A set and a dict are hash tables: in, insert and delete are O(1) average. A list‘s in is a linear scan calling __eq__ on each element.
The wiki’s own caveats, which matter
wiki.python.org/moin/TimeComplexity is the reference, and it qualifies itself in two ways worth carrying:
- The average cases “assume parameters generated uniformly at random”. Your data is not random.
- dict and set worst cases are O(n) under collisions. In practice string hashing is randomised per process and this does not bite, but “O(1) always” is not the claim.
deque(maxlen=...) is the one people forget
from collections import deque
recent: deque[Event] = deque(maxlen=1000)
recent.append(event) # oldest is discarded automatically, O(1)
A bounded deque is a fixed-memory sliding window with no bookkeeping. The list version — items.append(x) then if len(items) > 1000: items.pop(0) — is correct, is O(window) per push rather than O(1), and is one refactor away from someone deleting the trim and creating an unbounded buffer. Half the “slow memory leak” reports in long-running services are a window whose trim was lost.
💡list.pop(0) on a list capped at 64 elements is not slow. So when does the "list as a queue" mistake actually cost you, and what does that tell you about how to read complexity claims?
click to reveal
It costs you when the list is long, because the cost of pop(0) is proportional to what remains — a 64-element list means moving 63 pointers, which is nothing. The disaster case is the unbounded queue: a producer appends, a consumer pops from the front, the queue backs up to 100,000 items, and each pop now memmoves 800 KB. The cost grows precisely when you are already behind, which is the worst possible shape for a failure.
The general lesson is that a complexity claim is meaningless without the size it applies to. “O(n) per operation” tells you nothing until you know whether n is 64 or 64 million, and whether n is bounded at all. That is why the question to ask in review is not “is this the fast container?” but “what bounds n here, and what happens when that bound is wrong?”
A bounded structure with a worse constant frequently beats an unbounded one with a better complexity, because the bound is the thing that makes the system’s behaviour predictable under load.
The typing angle, and the hole in it
A signature can document the complexity contract:
def filter_known(items: Iterable[str], known: AbstractSet[str]) -> list[str]:
return [x for x in items if x in known]
AbstractSet[str] says “I will do membership tests on this, so give me something that is fast at them”. Sequence[str] says “I will index and re-iterate”. Container[str] says only “I will use in“. A reviewer who reads types learns the access pattern from the signature.
But there is a hole the checker will not close. This type-checks and is a bug:
def filter_known(items: Iterable[str], known: Iterable[str]) -> list[str]:
return [x for x in items if x in known] # O(n*m) -- and consumes `known`
Iterable supports in, so nothing complains. If known is a list, every test is a linear scan. If known is a generator, the first in consumes it and every subsequent test is False — a silent wrong answer, not a slow one.
There is no annotation for “cheap membership”. AbstractSet is the closest thing, and using it is a convention, not an enforcement. Say so in review; the checker will not.