Complexity Cheat Sheet
Keep this page bookmarked. During an interview, being able to state the complexity of every operation on every common data structure is baseline — interviewers expect it instantly. Knowing the constants and the worst-case triggers separates a good answer from a great one.
Data Structure Operations
Structure | Access | Search | Insert | Delete | Notes |
|---|---|---|---|---|---|
Array (static) | O(1) | O(n) | O(n) | O(n) | Shift required for mid/front ops |
Dynamic Array | O(1) | O(n) | O(1) amort | O(n) | Amortized: occasional O(n) resize |
Singly Linked List | O(n) | O(n) | O(1) head | O(1) given ptr | No random access |
Doubly Linked List | O(n) | O(n) | O(1) | O(1) given ptr | Bidirectional traversal |
Stack | — | — | O(1) | O(1) | LIFO — top only |
Queue | — | — | O(1) | O(1) | FIFO — enqueue/dequeue |
Hash Table | O(1) avg | O(1) avg | O(1) avg | O(1) avg | O(n) worst (all collide) |
BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | AVL/Red-Black stay balanced |
BST (unbalanced) | O(n) | O(n) | O(n) | O(n) | Degrades to linked list on sorted input |
AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | Strict height balance |h_L - h_R| ≤ 1 |
Red-Black Tree | O(log n) | O(log n) | O(log n) | O(log n) | Relaxed balance, fewer rotations |
Min/Max Heap | O(1) top | O(n) | O(log n) | O(log n) | Only root is O(1); heapify O(n) |
Trie | — | O(m) | O(m) | O(m) | m = key length; O(ALPHABET × n) space |
Segment Tree | O(log n) | O(log n) | O(log n) | O(log n) | Range query in O(log n) |
Fenwick Tree | O(log n) | O(log n) | O(log n) | O(log n) | Prefix sum in O(log n), simpler than seg tree |
Graph (adj list) | — | O(V+E) | O(1) | O(E) | Standard for sparse graphs |
Graph (adj matrix) | O(1) | O(V) | O(1) | O(1) | Better for dense graphs, O(V^2) space |
Sorting Algorithms
Algorithm | Best | Average | Worst | Space | Stable? | Notes |
|---|---|---|---|---|---|---|
Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Best only with early-exit on sorted input |
Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Always O(n²) — no early exit possible |
Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Fast on nearly sorted; used for small n |
Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Guaranteed; extra O(n) space |
Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Worst on sorted input; randomize pivot |
Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | In-place, guaranteed; worse cache perf |
Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | k = value range; not comparison-based |
Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | k = number of digits; stable per digit pass |
Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n+k) | Yes | Best for uniformly distributed floats in [0,1] |
Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Production sort (Python, Java); merge + insertion |
Graph Algorithm Complexities
Algorithm | Time | Space | Use case |
|---|---|---|---|
BFS | O(V+E) | O(V) | Shortest path (unweighted), level order |
DFS | O(V+E) | O(V) | Cycle detection, topological sort, SCC |
Dijkstra's (binary heap) | O((V+E) log V) | O(V) | SSSP for non-negative weights |
Dijkstra's (Fibonacci heap) | O(E + V log V) | O(V) | Optimal theoretical; complex to implement |
Bellman-Ford | O(VE) | O(V) | SSSP with negative weights, detect negative cycles |
Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest path (dense graphs) |
Kruskal's MST | O(E log E) | O(V) | MST with sorting + DSU |
Prim's MST (heap) | O((V+E) log V) | O(V) | MST; better for dense graphs |
Topological Sort (Kahn) | O(V+E) | O(V) | DAG ordering |
Tarjan's SCC | O(V+E) | O(V) | Strongly connected components |
Dynamic Programming Patterns
Pattern | Time | Space (optimized) | Examples |
|---|---|---|---|
1D DP (linear) | O(n) | O(1) | Fibonacci, house robber, climbing stairs |
2D DP (grid) | O(mn) | O(n) | Unique paths, min path sum, coin change 2D |
Subset sum / 0-1 knapsack | O(n×W) | O(W) | Partition equal subset, target sum |
LCS / Edit distance | O(mn) | O(n) | Longest common subsequence, string alignment |
LIS | O(n²) / O(n log n) | O(n) | Longest increasing subsequence (patience sort) |
Interval DP | O(n³) | O(n²) | Matrix chain, burst balloons, palindrome partitioning |
Bitmask DP | O(2^n × n) | O(2^n) | TSP, assign tasks (n ≤ 20) |
Tree DP | O(n) | O(n) | Diameter, max independent set on tree |
Digit DP | O(digits × states) | O(states) | Count numbers with property in range [lo, hi] |
String Algorithm Complexities
Algorithm | Preprocessing | Search | Space | Use case |
|---|---|---|---|---|
Brute force | — | O(nm) | O(1) | Pattern of length m in text of length n |
KMP | O(m) | O(n) | O(m) | Single pattern matching |
Rabin-Karp | O(m) | O(n) avg / O(nm) worst | O(1) | Multiple pattern matching with hashing |
Z-Algorithm | O(n) | O(n) | O(n) | Pattern + text preprocessing, count occurrences |
Aho-Corasick | O(sum of patterns) | O(n + matches) | O(sum of patterns) | Multi-pattern matching |
Suffix Array | O(n log n) | O(m log n) | O(n) | All substrings, LRS, LCS |
Suffix Automaton | O(n) | O(m) | O(n) | All substrings, distinct count |
Space Complexity Reference
Structure / Algorithm | Space | Notes |
|---|---|---|
Recursive DFS on tree/graph | O(h) call stack | h = tree height; O(n) worst for skewed tree |
BFS queue | O(w) | w = max width of tree/graph level |
Merge sort | O(n) | Auxiliary array for merging |
Quick sort | O(log n) avg | Recursion stack; O(n) worst if unbalanced |
Hash Table | O(n) | Proportional to number of elements stored |
Trie | O(ALPHABET × n × m) | ALPHABET chars per node, n words of avg length m |
Segment Tree | O(4n) | Array implementation; tree has ~4n nodes |
Adjacency list | O(V + E) | Standard graph representation |
Adjacency matrix | O(V²) | Dense but constant-time edge lookup |