Big-O & the Python Toolkit cheatsheet

🧮 Big-O & the Python Toolkit

Read n, pick a target complexity, and choose the built-in that gets you there without a hidden O(n) loop.

Recognize the pattern

n ≤ 10⁵ → target O(n log n) or better; near 10⁶ prefer O(n) and measure
n around 1,000 → quadratic pair checks may fit; inspect the work per pair
n around 20 → consider subset search, counting the work for each subset too
Values up to 10⁹ with n small → avoid allocating by value; consider sorting or hashing
Repeated membership queries on a list of hashable values → build a set once
Removing from the front (queues, BFS, simulations) → collections.deque
Need the smallest / largest repeatedly while adding → heapq; lookups in a sorted list → bisect

Constraints → target complexity

Rough starting targets, not time-limit guarantees. Measure large inputs; expensive operations and multiple test cases can change what's practical.

n up to	Target	Typical tools
about 8	factorial search may fit	permutations
about 20	exponential search may fit	subsets
about 100	O(n³) may fit	triple loops
about 1,000	O(n²) may fit	pairs, 2D DP
10⁵	O(n log n) or better	sorting, hashing
10⁶	prefer O(n); measure	scans, efficient sorts
10⁹ as a numeric bound	O(log n) or O(1)	binary search, math

Track independent dimensions: r rows × c columns means O(rc) work for a full grid scan. A value bound is different from the number of input items.

Problem-solving checklist

Clarify: size of n, empty input, duplicates, negatives, what to return if there's no answer.
Examples: one normal, one edge case, by hand.
Brute force: say it and its Big-O.
Optimise: what's repeated? Sort, hash, two pointers, heap, prefix sums?
Code: clear names, talk as you go.
Test: trace examples, then empty / single / duplicates / negatives / max size. State time and space.

Reading Big-O off code

Sequential blocks add; keep the biggest term.
Independent n-by-m nested loops cost O(nm). Checking each pair i < j costs O(n²).
Count total inner-loop moves when a pointer never resets: nested syntax can still mean O(n).
Halving n to 1 or doubling 1 to n: O(log n).
Recursion: sum work across all calls. With O(1) work per call, two branches on n − 1 cost O(2ⁿ). Two half-size calls plus an O(n) merge cost O(n log n). Memoization counts distinct states.
Space: peak live structures plus recursion depth; report required output memory separately.
n list appends cost O(n) total: O(1) amortized each, even though a resize may cost O(n).
Hash costs below are averages for bounded-size keys; severe collisions can make one lookup O(n).

The toolkit

Python template

from collections import Counter, defaultdict, deque
import heapq, bisect

counts = Counter("mississippi")  # O(n)
top2 = counts.most_common(2)

groups: dict[int, list[str]] = defaultdict(list)
for w in ["hi", "yo", "hey"]:
    groups[len(w)].append(w)

q = deque([1, 2, 3])
q.append(4)
first = q.popleft()               # O(1)

heap = [5, 1, 4]
heapq.heapify(heap)               # O(n)
heapq.heappush(heap, 2)           # O(log n)
smallest = heapq.heappop(heap)    # O(log n)

max_heap = [-x for x in [5, 1, 4]]
heapq.heapify(max_heap)           # all negated
heapq.heappush(max_heap, -10)
largest = -heapq.heappop(max_heap)

xs = [1, 3, 3, 5]
lo = bisect.bisect_left(xs, 3)    # first >= 3
hi = bisect.bisect_right(xs, 3)   # first > 3

people = [("ana", 31), ("bo", 25)]
people.sort(key=lambda p: (-p[1], p[0]))

Hidden costs: slow → fast

Python template

nums = list(range(1000))
queries = [3, 999, 5000]

# O(n) per lookup -> O(q * n)
hits = [x for x in queries if x in nums]
# build once, O(1) average per lookup
seen = set(nums)
hits = [x for x in queries if x in seen]

# max() re-scans every iteration: O(n^2)
flags = [x == max(nums) for x in nums]
best = max(nums)                     # hoist it
flags = [x == best for x in nums]

# Avoid recursive total(xs[1:]): it copies.
# An iterative scan avoids copies and stack depth.
def total(xs: list[int]) -> int:
    result = 0
    for x in xs:
        result += x
    return result

# string building: join once
parts = [str(x) for x in nums]
text = ",".join(parts)

Operation costs

Operation	Time	Space
list append / pop() at end	O(1) amortized	—
list len / [i]	O(1)	O(1)
list pop(0) / insert(0, x)	O(n)	—
x in list / .index / .count / min / max / sum	O(n)	—
slice a[i:j] / list + list	O(k) for k items	O(k)
sort() / sorted()	O(n log n)	O(n)
dict lookup/update/delete; set in/add/remove	O(1) average; O(n) worst case	—
dict / set construction from n items	O(n) expected	O(k) distinct keys
deque append / appendleft / pop / popleft	O(1)	—
deque[i] (middle)	O(n)	—
heapq heappush / heappop	O(log n)	—
heapq heapify / heap[0]	O(n) / O(1)	—
bisect_left / bisect_right	O(log n)	—
bisect.insort	O(n) (shifts items)	—
Counter(iterable)	O(n) expected	O(k) distinct
Counter.most_common() (all k keys)	O(k log k)	O(k)
str len / s[i]	O(1)	O(1)
str slice with k characters	O(k)	O(k)
one-character membership in str	O(n)	O(1)
str s + t	O(len(s) + len(t))	O(len(s) + len(t))
str join of p pieces, N output characters	O(p + N)	O(N) output; up to O(p) references

Watch for

Repeating a full max(), sum(), .count() or list membership scan for each item costs O(n²). Hoist it or use a set / Counter.
Using a list as a queue: pop(0) is O(n). Use deque.popleft().
Passing nums[1:] into recursion copies the list at every level. Pass an index instead.
Repeated string += can copy growing prefixes. Collect pieces and join them once instead of relying on interpreter optimisations.
Deep recursion: Python stops at about 1000 frames, so recursing once per element on 10⁵ items crashes. Use a loop or an explicit stack.
Sorting adds O(n log n) worst-case time and O(n) temporary space. A sort key runs once per item but may itself be expensive; bisect search is O(log n), insort is O(n).