VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 00: The method and Big-O

Lesson 0.5 of 6 in this moduleFree

Python costs you must know: list, dict, set, deque, heapq

The real cost of every operation you'll use in interviews, why each costs what it does, and three problems where choosing the right built-in turns O(n²) into O(n): a queue, list intersection and building strings.

about 15 min 8 Python examples 3 quick checks

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.

list.insert(0, 5) on a list of six items shifts every item one place right, n moves for n items; deque.appendleft adds at the front without moving anything.
Diagram— list.insert(0, 5) on a list of six items shifts every item one place right, n moves for n items; deque.appendleft adds at the front without moving anything.

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).

python
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 popleft is 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).

a key is hashed to a large integer, reduced modulo the table size to a slot index, and the slot holds the key and value; lookup is O(1) on average.
Diagram— a key is hashed to a large integer, reduced modulo the table size to a slot index, and the slot holds the key and value; lookup is O(1) on average.

Requirements this creates:

  • Keys must be hashable and unchanging: str, int, float, tuple (of hashables) yes; list, dict, set no. 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.

python
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.

python
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:

python
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?

  1. Build two sets
  2. Nested loops
  3. Two pointers walking both lists: O(n + m) time with O(1) extra memory
  4. Sort both again
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.

a min-heap drawn as a tree and as the list heapq stores; the children of index i are at 2i + 1 and 2i + 2, and every parent is no larger than its children.
Diagram— a min-heap drawn as a tree and as the list heapq stores; the children of index i are at 2i + 1 and 2i + 2, and every parent is no larger than its children.
  • 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).
  • heapq is a min-heap; for a max-heap, store -x (or (-score, item) tuples).
python
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.

characters copied to build a 10,000-character string from 1,000 pieces: repeated concatenation can copy about 5 million characters (O(n²)), join copies 10,000 (O(n)).
Chart— characters copied to build a 10,000-character string from 1,000 pieces: repeated concatenation can copy about 5 million characters (O(n²)), join copies 10,000 (O(n)).
python
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.

python
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

python
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?

  1. O(n log n), because insort is a binary search
  2. 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
  3. O(n)
  4. O(log n)
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."
  • "''.join because 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.

  1. Add a set seen for membership checks and keep out only for order: O(n) instead of O(n²)
  2. Use a tuple instead of a list for out
  3. Sort out after each append
  4. Use out.insert(0, x)
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

  1. Why is a[i] O(1) but a.insert(0, x) O(n) for a Python list?
  2. Why are dict and set lookups O(1) on average, and what makes a key hashable?
  3. Take "values in both lists" from brute force to sets to two pointers, with the constraint that justifies each.
  4. What does each heap operation cost, and how do you get a max-heap from heapq?
  5. Why can s += piece in a loop be O(n²), and what's always linear?
  6. What does bisect.insort really cost, and why?
Answers
  1. A list is a contiguous array of pointers: slot i's address is computed directly, but inserting at the front must shift every element.
  2. 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).
  3. 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.
  4. Peek O(1), push and pop O(log n), heapify O(n); store negated values for a max-heap.
  5. Strings are immutable, so each + may copy the whole growing string; ''.join(parts) copies each character once.
  6. O(n): the position is found in O(log n), but inserting into a list shifts elements.