Big-O Complexity Cheat Sheet: Algorithms and Data Structures
· Editorial team · 3 min read
cheatsheetbig-oalgorithmsdata-structuresinterview
Growth rates (best to worst)
| Notation | Name | Example | |---|---|---| | O(1) | Constant | Array index, hash lookup (average) | | O(log n) | Logarithmic | Binary search | | O(n) | Linear | Single scan | | O(n log n) | Linearithmic | Merge sort | | O(n²) | Quadratic | Nested loops, bubble sort | | O(2ⁿ) | Exponential | Naive subset or Fibonacci recursion | | O(n!) | Factorial | Permutations |
Data structures
| Structure | Access | Search | Insert | Delete | |---|---|---|---|---| | Array | O(1) | O(n) | O(n) | O(n) | | Dynamic array (end) | O(1) | O(n) | O(1) amortised | O(1) | | Linked list | O(n) | O(n) | O(1) at known node | O(1) at known node | | Stack / Queue | O(n) | O(n) | O(1) | O(1) | | Hash table | n/a | O(1) avg, O(n) worst | O(1) avg | O(1) avg | | Binary search tree | O(log n) avg, O(n) worst | same | same | same | | Balanced BST (AVL, red-black) | O(log n) | O(log n) | O(log n) | O(log n) | | Binary heap | peek O(1) | O(n) | O(log n) | O(log n) | | Trie | n/a | O(L) | O(L) | O(L) |
L is the key length.
Sorting
| Algorithm | Best | Average | Worst | Space | Stable | |---|---|---|---|---|---| | Bubble / Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes | | Selection | O(n²) | O(n²) | O(n²) | O(1) | No | | Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | | Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No | | Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No | | Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
Comparison sorts cannot beat O(n log n).
Graph algorithms
| Algorithm | Time | |---|---| | BFS / DFS | O(V + E) | | Dijkstra (heap) | O((V + E) log V) | | Bellman-Ford | O(V·E) | | Topological sort | O(V + E) | | Union-Find (with path compression) | near O(1) per operation |
Quick analysis rules
- Sequential steps add; nested loops multiply.
- Halving the problem each step gives log n.
- Recursion with two branches and no memoisation is often exponential.
- Drop constants and lower-order terms: O(2n + 10) becomes O(n).
- Recursion stack depth counts toward space.
Key takeaways
Stop spending an hour tailoring each resume — get a tailored resume and cover letter for this job in seconds.
Tailor my resumeEditorial team
Writes practical guides for Indian job seekers. Part of the HireStraight editorial team. Subscribe via RSS.