A queue of one million tasks. Processing them took 58 seconds. Changing one line made it take 0.023 seconds.
All timings below are the best of 3 runs on Python 3.15.2, on an Apple M4.
Video version:
The code
tasks = list(range(1_000_000))
while tasks:
task = tasks.pop(0) # take the oldest task
# ... process it
First in, first out. It looks fine, and with a few hundred tasks you'd never notice a problem.
Measured
| Items | list.pop(0) |
deque.popleft() |
|---|---|---|
| 10,000 | 0.004 s | 0.0002 s |
| 100,000 | 0.548 s | 0.0018 s |
| 1,000,000 | 57.96 s | 0.023 s |
Look at the left column: 10× more items, roughly 100× more time. That's the signature of O(n²). The deque column grows linearly: 10× the items, about 10× the time.
Why pop(0) is O(n)
A Python list is a dynamic array: one contiguous block of memory holding pointers.
# [ t0 | t1 | t2 | t3 | ... | t999999 ]
tasks.pop() # remove the end: nothing moves → O(1)
tasks.pop(0) # remove the front: 999,999 items move left → O(n)
Removing the first element leaves a gap, so every remaining element shifts one slot left. Do that n times and you get about n²/2 moves: half a trillion for a million tasks.
The fix: collections.deque
from collections import deque
tasks = deque(range(1_000_000))
while tasks:
task = tasks.popleft()
deque (double-ended queue) supports O(1) appends and pops at both ends. If you write breadth-first search, this is the queue to use.
Trap 2: insert(0, x)
The mirror image has the same cost: inserting at the front shifts everything right.
items = []
for i in range(100_000):
items.insert(0, i) # 1.377 s
items = deque()
for i in range(100_000):
items.appendleft(i) # 0.002 s
Trap 3: out = out + [x]
out = []
for i in range(50_000):
out = out + [i] # 1.988 s: builds a NEW list and copies everything
out = []
for i in range(50_000):
out.append(i) # 0.0007 s
out + [i] creates a brand-new list every iteration. out.append(i) and out += [i] modify the list in place (+= took 0.002 s in my test).
Trap 4 (half a myth): str +=
You'll often read that building a string with += in a loop is O(n²). I measured 300,000 iterations of s += 'x':
| Case | Time |
|---|---|
| plain local variable | 0.008 s |
with another reference (alias = s in the loop) |
0.665 s |
on an attribute (obj.s += 'x') |
0.658 s |
CPython has an optimization: when the string has only one reference, += can resize it in place. That's why the plain case is fast. As soon as anything else holds a reference, or the target is an attribute, the optimization can't apply, and every += copies the whole string: about 80× slower here. Other Python implementations (like PyPy) don't promise this optimization at all.
The reliable pattern:
parts = []
for chunk in chunks:
parts.append(chunk)
result = "".join(parts)
Recap
-
list.pop(0)andlist.insert(0, x)are O(n). Usedeque.popleft()/deque.appendleft(). -
out = out + [x]copies the list. Useappendor+=. -
s += ...is only fast on a plain local string. Build strings with"".join(parts). - Warning sign: 10× more data, ~100× slower means O(n²) is hiding somewhere.
Now go search your code for pop(0). 👀
I post one tested coding tip every day on YouTube at Refactorly. The 30-second version of this one is here.
Top comments (0)