Big O Complexity Reference
time and space complexity for every data structure and algorithm
complexity overview (fastest → slowest)
data structures
| Structure |
Access | Search | Insert | Delete |
Space | Notes |
| Array | O(1) | O(n) | O(n) | O(n) | O(n) | append O(1), middle O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(1) insert at head/tail |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | push/pop at top only |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) | enqueue/dequeue only |
| Hash Map | O(1)* | O(1)* | O(1)* | O(1)* | O(n) | *average. O(n) worst case |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | unbalanced: O(n) worst |
| Heap (binary) | O(1) | O(n) | O(log n) | O(log n) | O(n) | O(1) peek min/max |
| Trie | O(m) | O(m) | O(m) | O(m) | O(n*m) | m = key length |
sorting algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✓ |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ✗ |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✓ |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ✗ |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ✗ |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | ✓ |
common operations
| Operation | Complexity | Structure |
|---|
| Binary search (sorted array) | O(log n) | array |
| BFS / DFS | O(V + E) | graph (V=vertices, E=edges) |
| Dijkstra shortest path | O((V+E) log V) | weighted graph + heap |
| Dynamic programming (memoized) | O(n * states) | depends on problem |
| str.substring / slice | O(n) | string |
| Set lookup / Map lookup | O(1) | hash set / hash map |
| Array.sort() (V8) | O(n log n) | Timsort (merge + insertion) |