Big-O Complexity Cheatsheet
NewTime and space complexity reference for common data structures and algorithms.
Big-O complexity cheatsheet
Time & space complexity reference
Average and worst-case time complexity, plus space complexity, for common data structures and algorithms. Filter to find one quickly.
Data structures
| Structure / operation | Average | Worst | Space |
|---|---|---|---|
| Array (access) | O(1) | O(1) | O(n) |
| Array (search) | O(n) | O(n) | O(n) |
| Array (insert/delete at end) | O(1) | O(1) | O(n) |
| Array (insert/delete at start/middle) | O(n) | O(n) | O(n) |
| Linked List (access) | O(n) | O(n) | O(n) |
| Linked List (insert/delete at head) | O(1) | O(1) | O(n) |
| Hash Map (access/search) | O(1) | O(n) | O(n) |
| Hash Map (insert/delete) | O(1) | O(n) | O(n) |
| Binary Search Tree (balanced) | O(log n) | O(n) | O(n) |
| Binary Heap (insert/delete) | O(log n) | O(log n) | O(n) |
| Binary Heap (peek min/max) | O(1) | O(1) | O(n) |
| Stack / Queue (push/pop) | O(1) | O(1) | O(n) |
| Trie (search/insert) | O(k) (k = key length) | O(k) | O(n·k) |
Algorithms
| Algorithm | Average | Worst | Space |
|---|---|---|---|
| Binary Search | O(log n) | O(log n) | O(1) |
| Linear Search | O(n) | O(n) | O(1) |
| Bubble Sort | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n²) | O(log n) |
| Heap Sort | O(n log n) | O(n log n) | O(1) |
| Counting Sort | O(n + k) | O(n + k) | O(k) |
| Depth-First Search (graph/tree) | O(V + E) | O(V + E) | O(V) |
| Breadth-First Search (graph/tree) | O(V + E) | O(V + E) | O(V) |
| Dijkstra's Algorithm (binary heap) | O((V + E) log V) | O((V + E) log V) | O(V) |
| Dynamic Programming (typical 2D table) | O(n·m) | O(n·m) | O(n·m) |
Frequently Asked Questions
Why do hash map operations show O(1) average but O(n) worst case?
Hash maps degrade to O(n) only under pathological hash collisions where many keys land in the same bucket. In practice, with a decent hash function, O(1) is what you should expect.
Why is quicksort O(n²) worst case if it's usually the fastest sort in practice?
Quicksort's worst case happens with a poor pivot choice on already-sorted or adversarial input, degrading to O(n²). Its average case of O(n log n) with good pivot selection (like median-of-three) is why it outperforms merge sort in most real workloads despite merge sort having a better worst case.
What does the filter box search by?
It matches against the structure or algorithm name only (not the complexity values), so typing "sort" shows every sorting algorithm row across both tables.
Are these figures for a single operation or the whole structure?
Per-operation. Each row is scoped to one specific operation (like "insert" or "search"), because the same structure can have very different complexities for different operations — see how Array access is O(1) but Array search is O(n).
Why isn't there a row for every possible algorithm?
This covers the ones developers look up most often for interviews and everyday complexity reasoning — sorting, searching, and graph traversal fundamentals — rather than trying to be an exhaustive algorithms textbook.