You'll write every solution in this roadmap in Python. Python hides a lot: x in items looks like one step,
queue.pop(0) looks harmless, s += piece looks free. Each can quietly turn an O(n) algorithm into O(n²). This
lesson gives the cost of every operation you'll use, explains why each costs what it does (so you can reason
about new ones), and works three problems where the right built-in changes the complexity class.
1. The cost table
| Structure | Operation | Cost | Why |
|---|---|---|---|
list |
a[i], a[i] = x, len(a) |
O(1) | contiguous array of pointers: jump straight to slot i |
a.append(x), a.pop() |
O(1) amortised | spare capacity at the end (lesson 0.2) | |
a.insert(0, x), a.pop(0) |
O(n) | every element shifts one place | |
x in a, a.index(x), a.remove(x), a.count(x) |
O(n) | linear scan | |
a[i:j], a + b, list(a) |
O(length copied) | builds a new list | |
a.sort(), sorted(a) |
O(n log n) | Timsort; very fast on partly sorted data | |
dict / set |
d[k], k in d, d[k] = v, s.add(x) |
O(1) average | hash to a slot |
| iterate all items | O(n) | ||
s & t, s | t |
O(min) / O(len s + len t) | one lookup per element | |
collections.deque |
append, appendleft, pop, popleft |
O(1) | linked blocks; both ends are cheap |
d[i] in the middle |
O(n) | must walk the blocks | |
heapq (on a list) |
heappush, heappop, heapreplace |
O(log n) | sift along one root-to-leaf path |
h[0] (smallest) |
O(1) | the root | |
heapify(a) |
O(n) | bottom-up build | |
nsmallest(k, a) |
O(n log k) | keeps a size-k heap | |
bisect (on a sorted list) |
bisect_left(a, x) |
O(log n) | binary search |
insort(a, x) |
O(n) | the search is O(log n), the insert shifts elements | |
str |
s[i], len(s) |
O(1) | |
s + t, s[i:j], s.replace(...) |
O(length) | strings are immutable: always a new string | |
''.join(parts) |
O(total length) | one allocation, one copy |
You don't need to memorise this. Derive it from how the structure is laid out, which is what the next sections show.
2. Lists: great at the end, slow at the front
A Python list is a contiguous block of pointers. That's why a[i] is O(1): the address of slot i is computed
directly. It's also why inserting at the front is O(n): to make room at index 0, every element must move.
Worked problem: process tasks in arrival order (a queue)
Problem. Tasks arrive in a list; process them first-in, first-out, where processing a task may add new tasks to the back. (This is exactly the shape of breadth-first search, module 11.)
Brute force: use a list and pop(0).
import time
from collections import deque
def process_with_list(n):
queue = list(range(n))
done = 0
while queue:
task = queue.pop(0) # O(n): shifts every remaining element left
done += 1
if task % 3 == 0 and task < n:
queue.append(task + n) # occasionally a task spawns a follow-up
return done
def process_with_deque(n):
queue = deque(range(n))
done = 0
while queue:
task = queue.popleft() # O(1)
done += 1
if task % 3 == 0 and task < n:
queue.append(task + n)
return done
n = 60_000
assert process_with_list(n) == process_with_deque(n)
t0 = time.perf_counter(); process_with_list(n); slow = time.perf_counter() - t0
t0 = time.perf_counter(); process_with_deque(n); fast = time.perf_counter() - t0
print(f"list.pop(0): {slow:.2f} s, deque.popleft(): {fast:.3f} s")
assert fast < slow
- List: each
pop(0)is O(n) and there are n of them: O(n²). - Deque: each
popleftis O(1): O(n). - When the list is fine: if the queue never exceeds a few hundred items, the shift is cheap and either works. The constraint (queue size) decides, as always.
3. Dicts and sets: hashing buys O(1) lookups
A dict or set stores items in a table. To find a key, Python computes hash(key), maps it to a slot, and checks that
slot. The table's size doesn't matter: one hash, one probe (occasionally a few, when two keys collide).
Requirements this creates:
- Keys must be hashable and unchanging:
str,int,float,tuple(of hashables) yes;list,dict,setno. Need a list as a key? Convert it:tuple(sorted(xs)). - Average, not worst: if many keys collide, lookups degrade toward O(n). In practice Python's hashing makes this rare; say "O(1) average" in interviews.
Worked problem: which values appear in both lists?
Problem. Given two lists of sizes n and m, return the values present in both (each once).
ML context. Joining two datasets on a key; finding users present in both the training set and the evaluation set (a leakage check).
Brute force: for each value in a, scan b.
def common_brute(a, b):
out = []
for x in a:
if x in b and x not in out: # `in b` scans b: O(m); `in out` scans out
out.append(x)
return sorted(out)
assert common_brute([1, 2, 2, 3, 5], [2, 3, 4, 3]) == [2, 3]
print("brute force works")
Cost: O(n · m) (plus the out scans). With n = m = 10⁵, that's 10¹⁰: far too slow.
Optimisation 1, first principles: the repeated work is scanning b again for every x. Remember b in a
structure with O(1) membership: a set.
def common_sets(a, b):
return sorted(set(a) & set(b)) # build two sets O(n + m), intersect O(min(n, m))
assert common_sets([1, 2, 2, 3, 5], [2, 3, 4, 3]) == [2, 3]
print("set version works")
- Time: O(n + m) to build, plus O(k log k) to sort k results. Space: O(n + m).
Optimisation 2, when the constraints change: if both lists are already sorted and memory is tight, walk them together with two pointers, O(1) extra:
def common_sorted(a, b):
"""a and b must be sorted."""
i = j = 0
out = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
i += 1
elif a[i] > b[j]:
j += 1
else:
if not out or out[-1] != a[i]: # skip repeats in the output
out.append(a[i])
i += 1
j += 1
return out
import random
def common_brute(a, b): # from above, repeated so this block runs alone
out = []
for x in a:
if x in b and x not in out:
out.append(x)
return sorted(out)
def common_sets(a, b):
return sorted(set(a) & set(b))
rng = random.Random(11)
for _ in range(300):
a = sorted(rng.randint(0, 30) for _ in range(rng.randint(0, 20)))
b = sorted(rng.randint(0, 30) for _ in range(rng.randint(0, 20)))
assert common_sorted(a, b) == common_sets(a, b) == common_brute(a, b)
print("all three agree")
| If the constraint becomes… | Approach | Time | Extra space |
|---|---|---|---|
| Small lists | Brute force | O(n · m) | O(1) |
| Unsorted, memory fine | Sets | O(n + m) | O(n + m) |
| Both sorted, memory tight | Two pointers | O(n + m) | O(1) |
| One list tiny (m ≪ n) | Set of the small one, scan the big one | O(n + m) | O(m) |
| Too big for one machine | Hash-partition both by key, intersect each partition | distributed | per partition |
The last row is exactly how distributed data joins work: hash both sides on the key so matching keys meet on the same machine.
Quick check
Both lists are sorted, each has 10⁸ elements, and you have little spare memory. Which approach fits?
Show the answer
C. Two pointers walking both lists: O(n + m) time with O(1) extra memory — Sortedness is free structure: it lets two pointers find matches in one pass without storing either list.
4. Heaps: always know the smallest
heapq keeps a list arranged as a binary heap: a tree stored in array order where every parent is no larger
than its children. The smallest item sits at index 0.
- Peek the smallest: O(1).
- Push or pop: O(log n), because the item moves along one root-to-leaf path, and a balanced tree of n items is log n tall.
- Build a heap from a list with
heapify: O(n) (cleverer than n pushes). heapqis a min-heap; for a max-heap, store-x(or(-score, item)tuples).
import heapq
scores = [0.12, 0.91, 0.45, 0.88, 0.33, 0.97, 0.05]
# Top 3 scores: brute force sorts everything, O(n log n).
top3_sorted = sorted(scores, reverse=True)[:3]
# Heap: keep only 3 candidates, O(n log k).
top3_heap = heapq.nlargest(3, scores)
assert top3_heap == top3_sorted == [0.97, 0.91, 0.88]
# Max-heap by negation: always pop the current best.
h = [-s for s in scores]
heapq.heapify(h) # O(n)
assert -heapq.heappop(h) == 0.97 # O(log n)
assert -h[0] == 0.91 # peek, O(1)
print("heap operations work")
ML context: top-k retrieval in recommenders, k-nearest neighbours, beam search in sequence decoding: all heaps (module 09).
5. Strings are immutable
A string never changes. s + t builds a new string of length len(s) + len(t). So building a long string with +=
in a loop can copy the growing string every time.
pieces = [f"token{i:04d}" for i in range(1000)] # 1,000 pieces of 9 characters
# Risky: may copy the growing string on every +=, O(total²) in the worst case.
s = ""
for p in pieces:
s += p
# Always linear: one allocation, one copy of each character.
t = "".join(pieces)
assert s == t and len(t) == 9000
print("join builds the same string in one pass")
CPython sometimes optimises s += p in place when nothing else references s, so it may look fast. Don't rely on
it: it isn't guaranteed and fails as soon as another reference exists. ''.join(parts) is always O(total length).
6. Sorted lists and bisect
bisect.bisect_left(a, x) finds where x would go in a sorted list in O(log n) (binary search, module 05). But
bisect.insort(a, x) is O(n), because inserting into the middle of a list shifts elements.
import bisect
latencies = sorted([12, 45, 7, 88, 23, 51, 9, 30]) # O(n log n), once
def count_at_most(sorted_vals, x):
return bisect.bisect_right(sorted_vals, x) # O(log n) per query
assert count_at_most(latencies, 30) == 5 # 7, 9, 12, 23, 30
assert count_at_most(latencies, 5) == 0
assert count_at_most(latencies, 100) == 8
print("each query is a binary search")
Constraint check: many queries on fixed data → sort once, binary search each query. Many insertions mixed with
queries → insort is O(n) each, so with 10⁵ insertions you'd want a balanced tree or a sorted-container structure;
say so if asked.
7. Two helpers you'll use constantly
from collections import Counter, defaultdict
words = "the cat and the hat and the bat".split()
counts = Counter(words) # O(n): frequency of each word
assert counts["the"] == 3 and counts.most_common(1) == [("the", 3)]
by_length = defaultdict(list) # missing keys start as []
for w in words:
by_length[len(w)].append(w)
assert by_length[3] == ["the", "cat", "and", "the", "hat", "and", "the", "bat"]
print("Counter and defaultdict work")
Counter is a dict of counts; most_common(k) uses a heap, O(n log k). defaultdict removes the "is the key there
yet?" boilerplate. Both are dicts underneath: O(1) average per operation.
Quick check
A solution loops over 10⁵ items and calls bisect.insort(sorted_list, x) for each. What's its complexity, and why might it still be acceptable?
Show the answer
B. O(n²) in the worst case, because each insert shifts elements; it can be acceptable in practice because the shift is a fast memory move, but say the true complexity and when you'd switch structures — Finding the position is O(log n), but inserting into a Python list is O(n). Name the real cost before arguing it's fine.
8. Saying it out loud
When you pick a structure, say why in one line:
- "A deque, because I pop from the front: O(1) instead of O(n) for
list.pop(0)." - "A set for membership: O(1) average instead of scanning a list."
- "A heap of size k: O(n log k) instead of sorting everything."
- "
''.joinbecause strings are immutable and+=can be quadratic."
Quick check
Which change most improves this loop? out = [] then for x in stream: if x not in out: out.append(x) over 10⁶ items.
Show the answer
A. Add a set seen for membership checks and keep out only for order: O(n) instead of O(n²) — The hidden O(n) scan in x not in out is the bottleneck; a set makes each check O(1) on average.
Check yourself
- Why is
a[i]O(1) buta.insert(0, x)O(n) for a Python list? - Why are dict and set lookups O(1) on average, and what makes a key hashable?
- Take "values in both lists" from brute force to sets to two pointers, with the constraint that justifies each.
- What does each heap operation cost, and how do you get a max-heap from
heapq? - Why can
s += piecein a loop be O(n²), and what's always linear? - What does
bisect.insortreally cost, and why?
Answers
- A list is a contiguous array of pointers: slot i's address is computed directly, but inserting at the front must shift every element.
- The key is hashed to a slot, so lookup cost doesn't depend on size; keys must be immutable and implement hashing (str, int, tuple yes; list, dict, set no).
- Brute force scans the second list per element, O(n · m); sets remember one list for O(1) checks, O(n + m) time and space; if both are sorted and memory is tight, two pointers give O(n + m) with O(1) extra.
- Peek O(1), push and pop O(log n), heapify O(n); store negated values for a max-heap.
- Strings are immutable, so each
+may copy the whole growing string;''.join(parts)copies each character once. - O(n): the position is found in O(log n), but inserting into a list shifts elements.