| Data Structure | Operation | Worst Case | Average Case | Notes |
|---|---|---|---|---|
| Array / Dynamic Array | Access | O(1) | O(1) | Direct index arithmetic |
| Search | O(n) | O(n) | Linear scan | |
| Insert/Delete at end | O(n) | O(1) amortised | Occasional resize cost | |
| Insert/Delete at arbitrary pos | O(n) | O(n) | Shifting elements | |
| Singly Linked List | Access / Search | O(n) | O(n) | Nodeâbyânode traversal |
| Insert/Delete at head | O(1) | O(1) | Reassign head pointer | |
| Insert/Delete at tail | O(n) | O(n) | Unless a tail reference is maintained | |
| Doubly Linked List | Access / Search | O(n) | O(n) | |
| Insert/Delete given node | O(1) | O(1) | Pointer surgery with prev/next | |
| Stack (arrayâbacked) | Push / Pop | O(1) | O(1) | |
| Queue (array or list) | Enqueue / Dequeue | O(1) | O(1) | |
| Hash Table (Map / dict) | Search / Insert / Delete | O(n) | O(1) average | Pathological collisions |
| Binary Search Tree (BST) | Search / Insert / Delete | O(n) | O(log n) average | Depends on balance |
| Balanced BST (AVL, RâB) | Search / Insert / Delete | O(log n) | O(log n) | Strict rebalancing |
| Binary Heap | Access Min/Max | O(1) | O(1) | Root is extremum |
| Insert / Remove Min/Max | O(log n) | O(log n) | Percolate up/down | |
| Build Heap (Floydâs) | O(n) | O(n) | Bottomâup heapify | |
| Graph (Adj. List) | BFS / DFS | O(VÂ +Â E) | O(VÂ +Â E) | Visit every vertex & edge |
| Check adjacency | O(deg(v)) | O(deg(v)) | Scan neighbour list | |
| Graph (Adj. Matrix) | BFS / DFS | O(V²) | O(V²) | Matrix scan dominates |
| Check edge | O(1) | O(1) | Direct lookup | |
| Iterate neighbours | O(V) | O(V) | Row scan | |
| Skip List | Search / Insert / Delete | O(n) | O(log n) average | Probabilistic multiâlevel links |
| BâTree (order m) | Search / Insert / Delete | O(log n) | O(log n) | Wide fanâout for disk/system I/O |
| Disjoint Set Union (UnionâFind) | ||||
| find / union | ||||
| O(Îą(n)) | ||||
| O(1) amortised | ||||
| Îą(n) is inverse Ackermann (practically constant with path compression & union by rank) | ||||
| Paradigm / Pattern | Typical Task | Time Complexity (rough) | When to Use / Notes |
|---|---|---|---|
| Divide & Conquer | e.g. merge sort, fast exponentiation | O(n log n), O(log n) | Split problem in half, recurse, then combine |
| Binary Search | search sorted array / answer space | O(log n) | must have monotonic or sorted property |
| Two Pointers | pair sums, reverse array, linked lists | O(n) | one head & tail (or slow/fast) to meet in middle |
| Sliding Window | longest substring, subarray sums | O(n) | dynamic window adjustââexpand/contractâ |
| Prefix Sum / Difference Array | range-sum queries, subarray sums | O(1) per query after O(n) | precompute cumulative totals |
| Monotonic Stack / Queue | Next Greater Element, sliding window | O(n) | maintain increasing/decreasing order |
| Backtracking (permutations) | generate all orderings | O(n¡n!) | n! leaves à O(n) build cost |
| Backtracking (subsets / combinations) | enumerate subsets or k-combos | O(2âżÂˇn) or O(C(n,k)¡k) | explore include/exclude branches |
| Dynamic Programming | knapsack, LIS, edit distance | depends on states (e.g. O(n²)) | memo/tabulate overlapping subproblems |
| Greedy Algorithms | interval scheduling, coin change | O(n log n) or O(n) | make locally optimal choices |
| Graph Traversal (BFS/DFS) | connectivity, bipartiteness | O(V+E) | use adjacency list for sparse graphs |
| Shortest Paths | Dijkstra, BellmanâFord | O(E log V), O(V¡E) | weighted graphs |
| Minimum Spanning Tree | Kruskal, Prim | O(E log E) | use DSU or priority queue |
| UnionâFind (DSU) | connectivity, cycle detection | O(Îą(n)) amortised | path compression + union by rank |
| Bit Manipulation | bitwise ops, masks, subset tricks | O(1) per op | xor/swaps, subset-iteration via mask & -mask |
| Randomization | reservoir sampling, shuffle | O(n) | when unbiased sampling is needed |
| String Hashing (RabinâKarp) | substring search, duplicate detection | O(n) average | rolling hash + mod arithmetic |
| Math & Number Theory | gcd/lcm, modular exp, primes | O(log n) per op | when problems involve divisibility or cycles |
With those tweaks, youâll have one of the most comprehensive, scan-friendly cheat sheets out there!