Big-O cheatsheet
Every complexity in this course on one page. Click a name to open the lesson where you build it. * amortised / average · † given a reference to the node
Data structures
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Dynamic array (push/pop end) | O(1) | O(n) | O(1)* | O(1) | O(n) |
| Singly linked list | O(n) | O(n) | O(1)† | O(1)† | O(n) |
| Stack / Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash table | — | O(1)* | O(1)* | O(1)* | O(n) |
| Binary search tree (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Binary search tree (degenerate) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Binary heap | O(1) min | O(n) | O(log n) | O(log n) | O(n) |
| Trie (word length L) | — | O(L) | O(L) | O(L) | O(Σ L) |
| Union-find | — | O(α(n)) | O(α(n)) | — | O(n) |
Algorithms
| Algorithm | Best | Average | Worst | Space | Note |
|---|---|---|---|---|---|
| Binary search | O(1) | O(log n) | O(log n) | O(1) | sorted input |
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | stable |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | ≤ n swaps |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | stable, great when nearly sorted |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | stable |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | in place, fastest in practice |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | in place, unstable |
| BFS / DFS | O(V + E) | O(V + E) | O(V + E) | O(V) | BFS = unweighted shortest path |
| Topological sort | O(V + E) | O(V + E) | O(V + E) | O(V) | DAGs only |
| Dijkstra (binary heap) | O((V+E) log V) | O((V+E) log V) | O((V+E) log V) | O(V) | no negative weights |
Want the intuition behind the notation? Start with lesson 01 — Big-O. Canonical: https://dsa.thebraincord.com/cheatsheet