PART 7 · PRACTICE, PREP FLOW AND REVISION
Complexity cheat sheet
FreeLesson 76 of 78
Every cost you will be asked to state, on one page. If you can fill this table from memory, the complexity questions are free marks.
Data structures
| Structure | Access | Search | Insert | Delete | Space | Best for |
|---|---|---|---|---|---|---|
| list (array) | O(1) | O(n) | O(1) end, O(n) front | O(1) end, O(n) front | O(n) | Ordered data, indexing |
| dict / set | O(1)* | O(1)* | O(1)* | O(1)* | O(n) | Lookups, counting, dedupe |
| deque | O(1) ends | O(n) | O(1) both ends | O(1) both ends | O(n) | Queues, windows, BFS |
| heap (heapq) | O(1) min | O(n) | O(log n) | O(log n) min | O(n) | Top-k, scheduling, merge k |
| sorted list + bisect | O(1) | O(log n) | O(n) | O(n) | O(n) | Static sorted lookups |
| balanced BST / B-tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Database indexes |
| linked list | O(n) | O(n) | O(1) at a node | O(1) at a node | O(n) | Rare in Python |
* average case. Worst case O(n) with heavy hash collisions, which you can mention but rarely need to worry about.
Algorithms
| Algorithm | Time | Space | Page |
|---|---|---|---|
| Binary search | O(log n) | O(1) | 50 |
| Sorting (Timsort, merge sort) | O(n log n) | O(n) | 51 |
| Counting sort | O(n + k) | O(k) | 51 |
| Two pointers, sliding window | O(n) | O(1) to O(k) | 45, 47 |
| Prefix sums | O(n) build, O(1) query | O(n) | 43, 46 |
| BFS / DFS on V nodes, E edges | O(V + E) | O(V) | 53, 54 |
| Topological sort (Kahn) | O(V + E) | O(V) | 54 |
| Top-k with a heap | O(n log k) | O(k) | 55, 59 |
| Merge k sorted streams | O(n log k) | O(k) | 61 |
| Subsets / permutations | O(2^n) / O(n!) | O(n) depth | 52 |
| DP over one dimension | O(n x choices) | O(n), often O(1) | 56 |
| Hash join of n and m rows | O(n + m) | O(smaller side) | 65 |
| Mistake when stating complexity | Say this instead |
|---|---|
| "It is O(n)" for a loop that calls x in some_list | O(n x m): the in on a list is its own loop (page 44) |
| Forgetting the sort you added | O(n log n) overall, even if the rest is O(n) |
| Calling recursion O(1) space | O(depth) for the call stack |
| O(n) for building a string with += in a loop | Up to O(n²) copying; join is O(n) |
| Ignoring the output size | Listing all subsets is at least O(2^n): the answer itself is that big |
Practice before you move on
- Cover the complexity column and fill it in from memory.
- Pick two rows of the table and write a snippet that times them.