Big-O Cheat Sheet
One page, every complexity number from this track in one place — with the Python-specific gotchas called out explicitly, since Python's convenient syntax can hide the true cost of an operation more easily than a language like Java does. This is meant to be the page you reread the morning of an interview — not a substitute for actually understanding why each number is what it is (that's what the other 28 lessons are for), but a fast way to check your memory or settle a "wait, is that O(n) or O(log n) again?" doubt.
Data Structures
| Data structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| list (unsorted) | O(1) | O(n) | O(1) amortized append*, O(n) insert(0, x) | O(1) pop(), O(n) pop(0) | O(n) |
| list (sorted) | O(1) | O(log n) via bisect | O(n) | O(n) | O(n) |
| Singly linked list | O(n) | O(n) | O(1)** | O(1)** | O(n) |
| Doubly linked list | O(n) | O(n) | O(1)** | O(1)** | O(n) |
| Stack (Python list) | O(n) | O(n) | O(1) append (push) | O(1) pop | O(n) |
| Queue (collections.deque) | O(n) | O(n) | O(1) appendleft/append (enqueue) | O(1) popleft (dequeue) | O(n) |
| dict / set | — | O(1) average, O(n) worst*** | O(1) average, O(n) worst*** | O(1) average, O(n) worst*** | O(n) |
| Binary Search Tree | O(log n) average, O(n) worst | O(log n) average, O(n) worst | O(log n) average, O(n) worst | O(log n) average, O(n) worst | O(n) |
| Heap (heapq) | O(1) for min only | O(n) for arbitrary element | O(log n) heappush | O(log n) heappop | O(n) |
* list.append(x) is O(1) amortized (occasional resize copies are
spread over many appends), but list.insert(0, x) is O(n) because
every existing element has to shift over.
** O(1) only once you already have a reference to the node — finding that position first is the
O(n) search above.
*** Worst case only under heavy hash collisions, which Python's hash function makes rare in
practice.
Algorithms
| Algorithm | Time (average) | Time (worst) | Space | Stable? |
|---|---|---|---|---|
| Linear search | O(n) | O(n) | O(1) | — |
| Binary search | O(log n) | O(log n) | O(1) | — |
| Bubble sort | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n²) | O(log n) average, O(n) worst | No |
| BFS | O(V + E) | O(V + E) | O(V) | — |
| DFS | O(V + E) | O(V + E) | O(V) | — |
| Dijkstra (heapq) | O(E log V) | O(E log V) | O(V + E) | — |
| Kruskal's MST | O(E log E) | O(E log E) | O(V + E) | — |
| Prim's MST (heapq) | O(E log V) | O(E log V) | O(V + E) | — |
In real Python code you'd almost always call the built-in sorted() / list.sort() (Timsort, O(n log n) worst case, stable) rather than hand-rolling bubble/selection/insertion/merge/quick sort — this table exists because interviews still test whether you understand how those classic algorithms work under the hood.
Common Big-O Growth Rates, Fastest to Slowest
| Notation | Name | Typical example from this track |
|---|---|---|
| O(1) | Constant | List index access, dict get (average case) |
| O(log n) | Logarithmic | Binary search, balanced BST/heap operations |
| O(n) | Linear | Linear search, single pass over a list |
| O(n log n) | Linearithmic | Merge sort, quick sort (average), Dijkstra/MST with heapq |
| O(n²) | Quadratic | Bubble/selection/insertion sort, naive nested-loop solutions |
| O(2ⁿ) | Exponential | Naive recursive Fibonacci, brute-force backtracking without pruning |