← All cheatsheets

System

Computer Science 101 — data structures, Big O, and when the choice matters

The core data structures and Big-O costs every engineer leans on — arrays, hash maps, sets, stacks, queues, trees, graphs, sorting, binary search, recursion, and the memory/concurrency basics — in Python, each with the one rule for when it is the right reach.

Docs-checkedcsbig-odata-structuresalgorithmspython

Quick reference — reach for these first

dict lookupval = d[KEY] # or KEY in dHash map get/insert/membership is O(1) average — the default for any key→value or 'have I seen this' check.
set dedupeunique = set(ITEMS)Unordered, unique, O(1) membership. Dedupe or intersect in O(n); never a list for 'x in seen'.
list vs dequefrom collections import deque; q = deque()list.append/pop end = O(1), but pop(0)/insert(0) = O(n). Use deque for O(1) at both ends (FIFO).
binary searchimport bisect; i = bisect.bisect_left(A, X)O(log n) on a SORTED sequence — 1M items in ~20 comparisons. Unsorted input gives wrong answers.
Big-O ladderO(1) < O(log n) < O(n) < O(n log n) < O(n^2)Growth, not wall-clock. At n=1M the gap between O(n) and O(n^2) is seconds vs hours.

Big-O growth curves

Big-O growth curvesOperations versus input size for O(1), O(log n), O(n), O(n log n), and O(n squared). Flatter curves cost less as n grows; O(n squared) blows up fastest.opsinput size n →O(1)O(log n)O(n)O(n log n)O(n²)

Text equivalent: Operations plotted against input size for five complexity classes. O(1) is a flat line along the bottom; O(log n) rises slowly and flattens; O(n) is a straight diagonal; O(n log n) curves up more steeply; O(n squared), drawn in accent, shoots almost straight up and exits the top of the chart while n is still small — flatter curves scale better as input grows.

Common tasks

Structure / concept · Python · When it matters (Big O)

Structure / conceptPythonWhen it matters (Big O)
Big O (growth, not speed)# cost as n→∞: O(1)<O(log n)<O(n)<O(n log n)<O(n^2)Describes how work scales with input, ignoring constants/hardware. Reach for it before choosing a structure.
Array / lista = [1,2,3]; a[0]; a.append(4)Index & append O(1) amortized; search / insert(0) O(n). Use for ordered, index-addressed sequences.
Hash map (dict)d = {}; d[KEY] = 1; KEY in dGet/set/membership O(1) average, O(n) worst. Use for key→value and fast lookup by id.
Setseen = set(); seen.add(X); X in seenAdd/membership O(1) avg; dedupe O(n). Use for uniqueness and fast 'have I seen this'.
Stack (LIFO)st = []; st.append(X); st.pop()Push/pop O(1). Use for undo, expression parsing, DFS, the call stack itself.
Queue (FIFO)from collections import deque; q = deque(); q.append(X); q.popleft()Enqueue/dequeue O(1). Use for BFS and ordered job processing. (list.pop(0) is O(n) — a trap.)
Treeclass Node:\n def __init__(s,v): s.v=v; s.left=s.right=NoneBalanced BST search/insert O(log n); unbalanced degrades to O(n). Use for sorted/hierarchical data, range queries.
Graph (adjacency list)g = {0:[1,2], 1:[2], 2:[]}BFS/DFS visit every node+edge: O(V+E). Use for networks, dependencies, shortest paths.
Sortingordered = sorted(A)Comparison sort (CPython Timsort) is O(n log n). Sort once to unlock O(log n) binary search.
Binary searchimport bisect; i = bisect.bisect_left(A, X)O(log n) but ONLY on sorted input. 1M rows → ~20 comparisons vs 1M for a linear scan.
Recursiondef fib(n): return n if n<2 else fib(n-1)+fib(n-2)Naive fib is O(2^n); @lru_cache memoization drops it to O(n). Watch depth (~1000 default).
Stack vs heap (memory)x = 5 # name lives in a stack frame; the object lives on the heapStack = call frames/locals, fast LIFO, bounded. Heap = objects, GC-managed. Deep recursion overflows the stack.
GIL: threads vs processesfrom concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutorGIL serializes Python bytecode: threads win for I/O-bound, processes for CPU-bound (true parallelism).
Race conditionwith lock:\n counter += 1Shared mutable state + concurrency = races; += is read-modify-write, not atomic. Guard with a Lock.

Dedupe 1M records: a set (O(n)) vs a list (O(n²))

O(n) vs O(n^2)

1
Build a million records with lots of duplicates
import time\ndata = [i % 100_000 for i in range(1_000_000)]
2
The right way — dedupe with a set (one pass, O(n))
t = time.perf_counter()\nuniq = set(data)\nprint(len(uniq), round(time.perf_counter()-t, 3))
# 100000 0.03   -> ~0.03s for the full 1,000,000 records
3
The O(n^2) trap — membership against a growing list (run on only 50k, or it won't finish)
small = data[:50_000]      # 50k distinct values\nt = time.perf_counter()\nseen = []\nfor x in small:\n    if x not in seen:       # each check rescans `seen`\n        seen.append(x)\nprint(len(seen), round(time.perf_counter()-t, 2))
# 50000 ~6.0   -> ~6s for just 50k; it grows with the SQUARE of n
4
Same answer, different complexity — the structure decides, not the CPU

Troubleshooting — symptom → first check → next check

SymptomFirst checkEstablishesNext check
Dedupe / 'x not in seen' loop takes minutes on ~1M rowsIs `seen` a list that you scan with `in` inside the loop?Nested membership-in-a-list is the classic accidental O(n^2) — each check rescans the whole list.Make `seen` a set: membership becomes O(1) and the whole pass O(n).
Membership test `x in my_list` is the hot spot in a profileWhat container type backs the lookup?list/tuple membership is a linear O(n) scan; it does not index by value.Convert to a set or dict keyed on that value for O(1) lookups.
A FIFO queue built on a list is slow under loadAre you dequeuing with `list.pop(0)` or inserting at index 0?Both shift every remaining element, so each op is O(n), making the queue O(n^2) overall.Switch to collections.deque — append/popleft are O(1).
Binary search misses items or returns a wrong indexIs the sequence actually sorted by the key you search on?bisect / binary search assume sorted input; on unsorted data results are undefined, not just slow.sorted() once up front (O(n log n)), then keep it ordered and bisect.
RecursionError: maximum recursion depth exceededHow deep does the recursion go vs sys.getrecursionlimit() (~1000)?Each call adds a stack frame; deep or missing-base-case recursion overflows the call stack.Add/verify the base case, convert to iteration, or memoize to cut depth and repeated work.
Threads don't speed up CPU-heavy workIs the workload CPU-bound or I/O-bound?The GIL lets only one thread run Python bytecode at a time — threads parallelize waiting, not computing.Use ProcessPoolExecutor / multiprocessing for CPU-bound work; keep threads for I/O.
'But dict is only O(1) on average — should I worry about the worst case?'Are keys ordinary immutable values (str/int/tuple) with sane hashing?For normal keys CPython dict/set are effectively O(1); O(n) worst case needs pathological hash collisions.No action for typical keys — just keep keys immutable and don't force a constant __hash__.