Essential Algorithms and Data Structures Reference
Asymptotic Notation (Growth Rates)
- O(f(n)) – Upper Bound (Worst Case)
- Ω(f(n)) – Lower Bound (Best Case)
- Θ(f(n)) – Tight Bound (Exact)
Growth Rate Hierarchy
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!)
Sorting Algorithms – Time Complexities
| Algorithm | Best Case | Worst Case | Stable | In-Place |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n2) | Yes | Yes |
| Selection Sort | O(n2) | O(n2) | No | Yes |
| Insertion Sort | O(n) | O(n2) | Yes | Yes |
| Merge Sort | O(n log n) | O(n log n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | No | Yes |
| Quicksort | O(n log n) | O(n2) | No | Yes |
Search Methods Complexity
- Linear Search: O(n) (Unsorted data)
- Binary Search: O(log n) (Sorted data)
- Hash Table (Average): O(1) (Unsorted data)
Data Structure Time Complexities
| Structure | Max Element (Max(S)) | Membership Check (Member(x)) |
|---|---|---|
| Ordered Array | Θ(n) | Θ(log n) |
| Descending Array | Θ(1) | Θ(log n) |
| Unordered Linked List | Θ(n) | Θ(n) |
| Binary Tree (Height n) | Θ(2n) | Θ(2n) |
| Balanced BST | Θ(log n) | Θ(log n) |
| Hash Table (Chaining) | Θ(1)* | Θ(1)* (*average case) |
Master Theorem Summary
Recurrence Relation: T(n) = aT(n/b) + f(n)
- Case 1: If f(n) = O(nlogb a – ε), then T(n) = Θ(nlogb a)
- Case 2: If f(n) = Θ(nlogb a), then T(n) = Θ(nlogb a log n)
- Case 3: If f(n) = Ω(nlogb a + ε), then T(n) = Θ(f(n)) (if regularity holds)
Master Theorem Examples
- T(n) = 4T(n/2) + n2 → Θ(n2 log n) (Case 2)
- T(n) = 3T(n/2) + n2 → Θ(n2) (Case 3)
- T(n) = 2T(n/2) + n log n → Θ(n log2 n) (Case 2)
Heap Operations (Min/Max Heap)
- Insert: O(log n)
- Remove Root: O(log n)
- Build Heap: O(n)
- Heapsort: O(n log n)
Hashing Methods (Open Addressing)
- Linear Probing: h(k) + i mod m
- Quadratic Probing: h(k) + i2 mod m
- Double Hashing: h1(k) + i * h2(k) mod m
- Separate Chaining: Linked list per slot
Graph Algorithms Complexity
- DFS / BFS Traversal: O(V + E)
- Shortest Path (Unweighted): BFS → O(V + E)
- Shortest Path (Weighted): Dijkstra → O(E log V)
- Minimum Spanning Tree (MST): Kruskal / Prim → O(E log V)
- Cycle Detection: DFS or Union-Find → O(V + E)
- Topological Sort (DAG): DFS → O(V + E)
NP-Completeness Reductions
Vertex Cover and Independent Set Reductions
- Vertex Cover ≤P Independent Set: VC size k → IS of size |V| – k
- Independent Set ≤P Vertex Cover: IS size s → VC of size |V| – s
Common Time Complexities – Quick Reference
- Binary Search: O(log n)
- Linear Search: O(n)
- Build Heap: O(n)
- Heapsort: O(n log n)
- Insert in Heap: O(log n)
- DFS / BFS: O(V + E)
- Hash Table (Average): O(1)
- Dijkstra’s (with heap): O(E log V)