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 lookup
val = 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 dedupe
unique = set(ITEMS)Unordered, unique, O(1) membership. Dedupe or intersect in O(n); never a list for 'x in seen'.list vs deque
from 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 search
import 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 ladder
O(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
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 / concept | Python | When 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 / list | a = [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 d | Get/set/membership O(1) average, O(n) worst. Use for key→value and fast lookup by id. |
| Set | seen = set(); seen.add(X); X in seen | Add/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.) |
| Tree | class Node:\n def __init__(s,v): s.v=v; s.left=s.right=None | Balanced 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. |
| Sorting | ordered = sorted(A) | Comparison sort (CPython Timsort) is O(n log n). Sort once to unlock O(log n) binary search. |
| Binary search | import 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. |
| Recursion | def 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 heap | Stack = call frames/locals, fast LIFO, bounded. Heap = objects, GC-managed. Deep recursion overflows the stack. |
| GIL: threads vs processes | from concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutor | GIL serializes Python bytecode: threads win for I/O-bound, processes for CPU-bound (true parallelism). |
| Race condition | with lock:\n counter += 1 | Shared 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 records3
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 n4
Same answer, different complexity — the structure decides, not the CPU
Troubleshooting — symptom → first check → next check
| Symptom | First check | Establishes | Next check |
|---|---|---|---|
| Dedupe / 'x not in seen' loop takes minutes on ~1M rows | Is `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 profile | What 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 load | Are 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 index | Is 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 exceeded | How 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 work | Is 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__. |
References
- CPython TimeComplexity — list / dict / set / deque costswiki.python.org
- collections — deque and other container datatypesdocs.python.org
- bisect — array bisection (binary search)docs.python.org
- Global Interpreter Lock (GIL) — glossarydocs.python.org
- Sorting HOW TO (Timsort, O(n log n))docs.python.org