🧠 Data Structures & Algorithms – Complexity + Why Cheat Sheet Quick reference for time/space complexity plus why & when to use each algorithm.
Perfect for interviews, revisions, and system thinking .
Algorithm
Best
Avg
Worst
Space
Why / When to use
Bubble Sort
O(n)
O(n²)
O(n²)
O(1)
Learning only; detect nearly sorted arrays
Selection Sort
O(n²)
O(n²)
O(n²)
O(1)
Minimal swaps; memory-constrained
Insertion Sort
O(n)
O(n²)
O(n²)
O(1)
Small or nearly sorted data
Merge Sort
O(n log n)
O(n log n)
O(n log n)
O(n)
Stable, predictable performance
Quick Sort
O(n log n)
O(n log n)
O(n²)
O(log n)
Fast in practice; in-place
Heap Sort
O(n log n)
O(n log n)
O(n log n)
O(1)
Guaranteed time, no extra memory
Counting Sort
O(n + k)
O(n + k)
O(n + k)
O(k)
Integers with small range
Radix Sort
O(nk)
O(nk)
O(nk)
O(n + k)
Fixed-length keys (IDs)
Algorithm
Time
Space
Why / When to use
Linear Search
O(n)
O(1)
Small or unsorted data
Binary Search
O(log n)
O(1)
Fast lookup on sorted arrays
Jump Search
O(√n)
O(1)
Sorted data, fewer comparisons
Interpolation Search
O(log log n)
O(1)
Uniformly distributed data
🧱 Data Structures – Operations
Operation
Time
Why / When
Access
O(1)
Fast index-based access
Search
O(n)
Unordered data
Insert/Delete
O(n)
Shifting elements
Operation
Time
Why / When
Access
O(n)
Sequential access
Insert/Delete
O(1)
Frequent insertions
Search
O(n)
No indexing
Operation
Time
Why / When
Push / Pop
O(1)
LIFO behavior (undo, recursion)
Enqueue / Dequeue
O(1)
FIFO processing (queues, jobs)
Operation
Avg
Worst
Why / When
Insert
O(1)
O(n)
Fast key-value lookup
Search
O(1)
O(n)
Caches, dictionaries
Delete
O(1)
O(n)
Index-like access
Operation
Time
Space
Why / When
DFS Traversal
O(n)
O(h)
Explore depth, recursion
BFS Traversal
O(n)
O(n)
Level-wise traversal
BST Search
O(log n)
O(1)
Ordered data lookup
AVL / RB Tree Ops
O(log n)
O(1)
Always balanced trees
h = tree height
Algorithm
Time
Space
Why / When
BFS
O(V + E)
O(V)
Shortest path (unweighted)
DFS
O(V + E)
O(V)
Cycle detection
Dijkstra
O((V + E) log V)
O(V)
Shortest path (weighted)
Bellman-Ford
O(VE)
O(V)
Negative edge weights
Floyd-Warshall
O(V³)
O(V²)
All-pairs shortest paths
Topological Sort
O(V + E)
O(V)
Dependency resolution
Union-Find
O(α(n))
O(n)
Dynamic connectivity
Problem
Time
Space
Why / When
Fibonacci
O(n)
O(n)
Overlapping subproblems
0/1 Knapsack
O(nW)
O(nW)
Choice optimization
LCS
O(nm)
O(nm)
Sequence comparison
LIS
O(n log n)
O(n)
Increasing subsequence
Coin Change
O(nW)
O(W)
Min/max combinations
🔂 Recursion & Backtracking
Problem
Time
Space
Why / When
Permutations
O(n!)
O(n)
All arrangements
Combinations
O(2ⁿ)
O(n)
Subset generation
N-Queens
O(n!)
O(n²)
Constraint satisfaction
Complexity
Why it matters
O(1)
Best possible
O(log n)
Scales well
O(n)
Linear growth
O(n log n)
Efficient sorting
O(n²)
Watch for nested loops
O(2ⁿ)
Explodes quickly
O(n!)
Bruteforce only
