Notes / GATE / Algorithms

CH 01

Complexity cheat sheet

Algorithms · GATE

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)
Done with this chapter? Now put it to use.Today's GATE question →