Algorithms & Data Structures
Average-case complexity for the data structures and algorithms you reach for in interviews — hash map O(1) average, balanced tree O(log n), comparison sort's O(n log n) floor — plus the worst cases that actually bite.
Updated August 30, 2026 · 5 min read
| Array — index access | O(1) |
|---|---|
| Array — search (unsorted) | O(n) |
| Dynamic array — append | O(1) amortizedO(n) on the resize |
| Dynamic array — insert/delete at index | O(n) |
| Hash map — insert / lookup / delete | O(1)O(n) worst: collisions / resize |
| Balanced BST — search / insert / delete | O(log n) |
| Binary heap — insert / delete-min | O(log n) |
| Binary heap — peek min/max | O(1) |
| Linked list — access by index | O(n) |
| Linked list — insert/delete at known node | O(1) |
| Sorted array — search | O(log n)binary search |
| Trie — lookup | O(L)L = key length |
| Comparison-sort lower bound | O(n log n) |
|---|---|
| Quicksort | O(n log n) avgO(n²) worst on bad pivots |
| Mergesort | O(n log n)stable, O(n) extra space |
| Heapsort | O(n log n)in-place, not stable |
| Counting / radix sort | O(n)bounded integer keys only |
| BFS / DFS | O(V + E) |
|---|---|
| Dijkstra (binary heap) | O((V + E) log V) |
| Binary search | O(log n) |
| Two-pointer / sliding window | O(n) |
| Topological sort | O(V + E) |