PYQ coming soon
EXAMhelp · GATE notes
Algorithms
CH 01Complexity cheat sheet
Key points
- Master theorem: T(n) = aT(n/b) + f(n); compare f(n) with n^(log_b a).
- Lower bound for comparison-based sorting is Ω(n log n).
- Dijkstra does not work with negative edges — use Bellman-Ford.
- Merge sort is stable; quick sort and heap sort are not.
Formulas & facts
- Merge sort
- O(n log n) in every case
- Quick sort
- Avg O(n log n), worst O(n²)
- Heap build
- O(n)
- Dijkstra (binary heap)
- O((V + E) log V)
- Bellman-Ford
- O(VE)
- Floyd-Warshall
- O(V³)
- Kruskal
- O(E log E)