Big-O Cheat Sheet
Time and space complexity of common data structures and sorting algorithms.
O(1) / O(log n) — excellent
O(n) / O(n log n) — acceptable
O(n²) — poor
Data Structures
| Structure | Access | Search | Insert | Delete | Space | Notes |
|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) | Fast access by index; slow insert/delete in middle |
| Dynamic Array | O(1) | O(n) | O(1)* | O(n) | O(n) | O(1)* amortised insert at end (e.g. Python list) |
| Singly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | Fast insert/delete at head; no random access |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | Same as singly but can traverse backwards |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | LIFO — push and pop from the top |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) | FIFO — enqueue at back, dequeue from front |
| Hash Table | N/A | O(1)* | O(1)* | O(1)* | O(n) | O(1)* average; O(n) worst case with collisions |
| Binary Search Tree | O(log n)* | O(log n)* | O(log n)* | O(log n)* | O(n) | O(log n) average; O(n) worst if unbalanced |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Self-balancing BST; guaranteed O(log n) |
| Min/Max Heap | O(1)** | O(n) | O(log n) | O(log n) | O(n) | **O(1) access to min/max only |
| Trie | O(k) | O(k) | O(k) | O(k) | O(nk) | k = key length; great for prefix searches |
| Graph (adj. list) | N/A | O(V+E) | O(1) | O(V+E) | O(V+E) | V = vertices, E = edges |
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable | Notes |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Simple but slow; educational use only |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Always O(n²); not suitable for large data |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Efficient for small or nearly-sorted data |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Reliable; good for linked lists; needs extra space |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Fast in practice; worst case with bad pivot choice |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | In-place; not cache-friendly |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | k = range of input; only for integers in small range |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | Fast for integers; k = number of digits |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Used in Python and Java; hybrid merge + insertion |