Big-O Cheat Sheet
One page, every complexity number from this track in one place. 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 |
| Array (unsorted) | O(1) | O(n) | O(n)* | O(n) | O(n) |
| Array (sorted) | O(1) | O(log n) | 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 (array/linked) | O(n) | O(n) | O(1) push | O(1) pop | O(n) |
| Queue (array/linked) | O(n) | O(n) | O(1) enqueue | O(1) dequeue | O(n) |
| HashMap / HashSet | — | 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 (min/max) | O(1) for min/max only | O(n) for arbitrary element | O(log n) | O(log n) for min/max | O(n) |
* Insert at the end (with spare capacity) is O(1) amortized; inserting at an arbitrary index requires shifting, O(n).
** O(1) only once you already have a reference to the node/position — finding that position first is the O(n) search above.
*** Worst case only under heavy hash collisions, which a good 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 (heap) | 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 (heap) | O(E log V) | O(E log V) | O(V + E) | — |
Reading "V" and "E": in graph algorithms, V is the number of vertices and E is the number of edges. O(V + E) means the cost scales with the total size of the graph — every vertex and every edge gets visited roughly once.
Common Big-O Growth Rates, Fastest to Slowest
| Notation | Name | Typical example from this track |
|---|
| O(1) | Constant | Array index access, HashMap get (average case) |
| O(log n) | Logarithmic | Binary search, balanced BST/heap operations |
| O(n) | Linear | Linear search, single pass over an array |
| O(n log n) | Linearithmic | Merge sort, quick sort (average), Dijkstra/MST with a heap |
| O(n²) | Quadratic | Bubble/selection/insertion sort, naive nested-loop solutions |
| O(2ⁿ) | Exponential | Naive recursive Fibonacci, brute-force backtracking without pruning |
Next up: Knowing the numbers is half the battle —
How to Approach a DSA Interview covers the framework for actually applying them under interview pressure.