PART 4 · DSA AND COMPLEXITY · CHAPTER 17

What Python operations really cost

FreeLesson 42 of 78

Half of all slow interview code is one innocent-looking line inside a loop. Learn the cost of the built-ins and you will spot it immediately.

Structure	Cheap: O(1) or O(log n)	Expensive: O(n) or worse	Watch out
`list`	xs[i], append, pop(), len	`x in xs`, insert(0, x), pop(0), remove(x), index(x), slicing O(k)	A list is an array, not a linked list
`dict`	d[k], d.get, k in d, set, delete	Iterating all keys, copying	Worst case O(n) with heavy hash collisions, rare in practice
`set`	add, remove, x in s	Union, intersection: O(len of inputs)	Items must be hashable
`collections.deque`	append, appendleft, pop, popleft	Indexing into the middle	Use it for queues and windows
`heapq`	push, pop: O(log n), peek heap[0]: O(1)	heapify is O(n); searching a heap is O(n)	Min-heap only; negate for max
`str`	len, s[i]	`s += x` in a loop, `sub in s`, replace, split	Strings are immutable: every change makes a copy
`sorted / list.sort`		O(n log n)	Sorting inside a loop is O(n² log n)
`bisect`	bisect_left: O(log n)	insort: O(n), because the list shifts	Only on a sorted list

ONE LINE, A HUGE DIFFERENCEPYTHON 3.12

import time
from collections import deque

n = 100_000
def ms(fn):
    t = time.perf_counter()
    fn()
    return (time.perf_counter() - t) * 1000

def drain_list():
    q = list(range(n))
    while q:
        q.pop(0)              # shifts every remaining item

def drain_deque():
    q = deque(range(n))
    while q:
        q.popleft()           # O(1)

print(f"list.pop(0)     {ms(drain_list):8.1f} ms")
print(f"deque.popleft() {ms(drain_deque):8.1f} ms")

Output

list.pop(0)        728.8 ms
deque.popleft()     10.5 ms

The times are what this run measured when the book was built. Yours will differ.

THE HIDDEN LOOP INSIDE "IN"PYTHON 3.12

orders = list(range(50_000))
vip_list = list(range(0, 50_000, 7))
vip_set = set(vip_list)

import time
t = time.perf_counter()
a = [o for o in orders if o in vip_list]     # O(n x m)
t1 = time.perf_counter()
b = [o for o in orders if o in vip_set]      # O(n)
t2 = time.perf_counter()
print(len(a) == len(b))
print(f"list {1000*(t1-t):.0f} ms, set {1000*(t2-t1):.1f} ms")

Output

True
list 3573 ms, set 2.0 ms

The times are what this run measured when the book was built. Yours will differ.

o in vip_list is a loop hiding inside a loop. Converting the list to a set once (O(m)) turns the whole filter from O(n x m) into O(n + m). This is the single most common fix in DE coding rounds.

Practice before you move on

Replace a list.pop(0) loop with collections.deque.popleft() and time both on 50,000 items.
Find a line in an earlier lesson where a membership test on a list could use a set instead.