What Python's built-ins cost
In Python you rarely build data structures from scratch: list, dict,
set, deque and heapq are already there, implemented in C. But each has
operations that are instant and operations that quietly walk the whole thing. Knowing which is
which is most of practical DSA in Python.
1. list: a dynamic array
| Operation | Cost | Note |
|---|---|---|
a[i], a[i] = x, len(a) | O(1) | direct address arithmetic |
a.append(x), a.pop() | O(1) amortised | at the end only |
a.insert(0, x), a.pop(0), del a[0] | O(n) | shifts everything; use deque |
x in a, a.index(x), a.count(x), a.remove(x) | O(n) | linear scan; use a set/dict for lookups |
a[i:j] | O(j − i) | copies the slice |
a + b, a.extend(b) | O(len(b)) (+ O(len(a)) for +) | + builds a new list |
a.sort(), sorted(a) | O(n log n) | Timsort; O(n) on already-sorted runs |
min(a), max(a), sum(a) | O(n) | calling it inside a loop makes O(n²) |
2. The front-of-list trap, measured
import timeit
from collections import deque
def drain_list(n):
q = list(range(n))
while q:
q.pop(0) # O(n) each → O(n²) total
def drain_deque(n):
q = deque(range(n))
while q:
q.popleft() # O(1) each → O(n) total
for n in (20_000, 40_000, 80_000):
t_list = timeit.timeit(lambda: drain_list(n), number=1)
t_deque = timeit.timeit(lambda: drain_deque(n), number=1)
print(f"n={n:>6,}: list.pop(0) {t_list * 1000:8.1f} ms deque.popleft() {t_deque * 1000:6.2f} ms")
Doubling n roughly quadruples the list version and doubles the deque version. A "queue" built on
list.pop(0) is one of the most common accidental O(n²)s in Python code, including BFS
implementations (lesson 17).
3. dict and set: hash tables
| Operation | Average | Worst |
|---|---|---|
d[k], d[k] = v, del d[k], k in d | O(1) | O(n) (pathological collisions; lesson 09) |
s.add(x), x in s, s.discard(x) | O(1) | O(n) |
s | t, s & t, s - t | O(len(s) + len(t)) / O(min) for & | |
iterate, list(d), d.copy() | O(n) |
import timeit
emails_list = [f"user{i}@example.com" for i in range(100_000)]
emails_set = set(emails_list)
probe = "[email protected]" # worst case for the list: at the very end
print(f"in list: {timeit.timeit(lambda: probe in emails_list, number=100) / 100 * 1e6:10.1f} µs")
print(f"in set: {timeit.timeit(lambda: probe in emails_set, number=100) / 100 * 1e6:10.3f} µs")
Dict keys and set members must be immutable-ish: ints, strings, tuples of those, frozen dataclasses.
Lists and dicts cannot be keys. To use a list as a key, convert it with tuple(lst); for a
set, use frozenset(s). Dicts keep insertion order (guaranteed since 3.7). Sets do not
keep any order.
4. Strings are immutable
import timeit
words = ["data"] * 50_000
def concat():
s = ""
for w in words:
s = s + w + "," # may copy the whole string each time
return s
def join():
return ",".join(words) + "," # one pass, one allocation
assert concat() == join()
print(f"concat: {timeit.timeit(concat, number=5) / 5 * 1000:.2f} ms")
print(f"join: {timeit.timeit(join, number=5) / 5 * 1000:.2f} ms")
str.join is the reliable O(n) way to build a string: here it is over a thousand times
faster. CPython can sometimes extend a string in place for the exact form s += x when nothing
else references s, but s = s + w + "," builds a temporary first and defeats that
trick, so every iteration copies the whole string: O(n²). Never rely on the optimisation. Other Pythons
do not have it, and a harmless-looking edit can switch it off. s[i] and len(s) are O(1); x in s
and s.find are O(n·m) in the worst case.
5. The rest of the toolbox
| Structure | Fast operations | Slow operations | Lesson |
|---|---|---|---|
collections.deque | append/pop at both ends O(1) | index in the middle O(n) | 08 |
heapq (on a list) | push/pop smallest O(log n), peek O(1), heapify O(n) | search/remove arbitrary O(n) | 15 |
bisect (on a sorted list) | find position O(log n) | insert still O(n) (shifting) | 10 |
collections.Counter | count updates O(1) | most_common(k) O(n log k) | 09 |
array, NumPy arrays | compact numeric storage, vectorised maths | growing one element at a time | 05 |
Recap
- list: O(1) at the end and by index; O(n) at the front, for
in,index,remove. - dict/set: O(1) average lookup, insert and delete. The default tool for "have I seen this?".
- deque for queues, heapq for "smallest next", bisect for sorted lookups.
"".jointo build strings; never rely on+=in a loop.- Hidden O(n) calls inside loops are the most common source of accidental O(n²).
Checkpoint
job = jobs.pop(0) on a list of 1 million jobs. What should it use?
pop(0) shifts every remaining element: O(n) each, O(n²) overall. A deque removes from the left in O(1) and keeps FIFO order. (pop() would take from the wrong end.)