Short notes: Algorithms
Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.
📈 Asymptotic Analysis & Recurrences🔀 Sorting & Searching🕸️ Graph Algorithms🧩 Algorithm Design: Divide & Conquer, Greedy, DP🧮 P, NP & NP-Completeness
Every algorithm question ends in a complexity. Loop counting, recurrences and the Master theorem are near-certain marks.
- Growth rates and Big-O, Ω, Θ. f = O(g) means f grows no faster than g, Ω(g) no slower, Θ(g) both. Order to remember: 1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ. Constants and lower-order terms vanish. Polynomials beat any power of log; exponentials beat any polynomial. log(n!) = Θ(n log n).→ Drop constants and small terms; constants in the exponent are NOT constants.
- Counting loop iterations. Multiply nested loop counts when they are independent. A loop that doubles (i *= 2) runs log n times. A loop whose inner bound depends on the outer index gives a sum: 1 + 2 + … + n = n(n + 1)/2 = Θ(n²), but 1 + 2 + 4 + … + n = Θ(n). A loop with i * i <= n runs √n times; i = √i runs log log n times.→ Doubling loop = log n; sums of 1..n = n²/2; sums of 1,2,4..n = 2n.
- Solving recurrences. A recursive algorithm gives a recurrence T(n). Three tools: substitution (guess then prove by induction), recursion tree (sum the work per level) and the Master theorem. Common ones: T(n) = T(n − 1) + n → Θ(n²); T(n) = T(n − 1) + 1 → Θ(n); T(n) = 2T(n − 1) + 1 → Θ(2ⁿ); T(n) = T(n/2) + 1 → Θ(log n); T(n) = T(√n) + 1 → Θ(log log n); T(n) = T(n/3) + T(2n/3) + n → Θ(n log n).→ T(n − 1) + n = n²; T(n/2) + 1 = log n; T(√n) + 1 = log log n; 2T(n − 1) + 1 = 2ⁿ.
- Master theorem. For T(n) = a·T(n/b) + Θ(nᵏ logᵖ n) with a ≥ 1, b > 1: compare log_b a with k. If log_b a > k then Θ(n^(log_b a)). If equal then Θ(nᵏ logᵖ⁺¹ n). If less then Θ(nᵏ logᵖ n). It does not apply when a is not a constant, when the subproblems have different sizes, or when f(n) is not polynomially related (e.g. n / log n).→ Compare log_b a with k: bigger = leaves, equal = extra log, smaller = root.
Formulas
Order of growth
1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ
Sums
1 + 2 + … + n = n(n + 1)/2; 1 + 2 + 4 + … + 2ᵏ = 2ᵏ⁺¹ − 1; 1 + 1/2 + 1/4 + … < 2; H_n = 1 + 1/2 + … + 1/n = Θ(log n)
Master theorem
T(n) = aT(n/b) + Θ(nᵏ logᵖ n): log_b a > k → Θ(n^(log_b a)); = k → Θ(nᵏ logᵖ⁺¹ n); < k → Θ(nᵏ logᵖ n)
Stirling
log(n!) = Θ(n log n); n! = Θ(√n (n/e)ⁿ)
Log rules
log_a b = log_c b / log_c a, so all log bases differ by a constant factor. 2^(log₂ n) = n
What GATE asks
- ★★★Order functions by asymptotic growth. Rank f(n) like n^(log n), 2^(√n), n!, (log n)^(log n) and pick the correct increasing order.
- ★★★Time complexity of a nested loop / recursive code. Count iterations; watch for doubling variables and inner bounds that depend on the outer index.
- ★★★Solve a recurrence. Master theorem or recursion tree, including T(n) = T(√n) + 1 and unequal splits.
- ★★★True or false: f = O(g), f = Θ(g). Compare exponentials with polynomials, and log bases inside exponents (2^(2n) vs 2^n).
Traps
2^(2n) is not O(2ⁿ) (it equals 4ⁿ), but 2^(n + 1) is. Constants in the exponent matter.
log(n!) is Θ(n log n) but n! itself is far bigger than any exponential cⁿ.
The Master theorem needs a constant a and b: T(n) = 2ⁿT(n/2) + nⁿ is outside it.
Big-O is an upper bound only: saying "quick sort is O(n³)" is true but useless.
Complexities, stability, number of swaps and comparisons, and quicksort partitioning appear in almost every paper.
- Elementary sorts: bubble, insertion, selection. Bubble: repeatedly swap adjacent out-of-order pairs; Θ(n²) comparisons (best case n − 1 with an early-exit flag). Insertion: insert each element into the sorted prefix; best O(n), worst O(n²), and the number of shifts equals the number of inversions. Selection: pick the minimum each pass; always n(n − 1)/2 comparisons but only n − 1 swaps. Bubble and insertion are stable; selection is not.→ Bubble/insertion are stable; selection has at most n − 1 swaps; insertion shifts = inversions.
- Merge sort. Divide into halves, sort each, merge in linear time: T(n) = 2T(n/2) + n = Θ(n log n) in every case. Needs O(n) extra space and is stable. Merging two sorted lists of sizes m and n takes at most m + n − 1 comparisons. Good for linked lists and external sorting.→ Merge sort: always n log n, stable, O(n) extra space.
- Quick sort. Choose a pivot, partition into smaller and larger, recurse. Average and best Θ(n log n); worst Θ(n²) when the pivot is always an extreme (already sorted input with a first or last pivot, or all-equal keys with a naive partition). T(n) = T(n − 1) + n. Not stable, in place (O(log n) stack on average). A median pivot gives T(n) = 2T(n/2) + n.→ Quick sort: average n log n, worst n² (sorted input with a first/last pivot), not stable.
- Heap sort and non-comparison sorts. Heap sort: build a max-heap in O(n), then extract n times: Θ(n log n) always, in place, not stable. Counting sort sorts n integers in range 0..k in Θ(n + k) and is stable. Radix sort sorts d-digit numbers with a stable pass per digit in Θ(d(n + k)). Bucket sort is O(n) on average for uniformly spread input.→ Heap sort: n log n, in place, unstable. Counting: n + k, stable.
- Lower bound and comparison summary. Any comparison sort needs Ω(n log n) comparisons in the worst case, because a decision tree with n! leaves has height ≥ log₂(n!) = Θ(n log n). Know the table: best, average, worst, extra space and stability of every sort. Sorting is also the engine behind many problems (duplicates, closest pair, interval merging).→ Comparison sorts: Ω(n log n) from n! leaves.
- Binary search and selection. Binary search on a sorted array takes ⌊log₂ n⌋ + 1 probes in the worst case. It needs random access. Selection (k-th smallest) can be done in expected O(n) with quickselect and worst-case O(n) with median of medians. Finding the minimum takes n − 1 comparisons; finding both min and max takes ⌈3n/2⌉ − 2.→ Binary search: ⌊log₂ n⌋ + 1; min-max: ⌈3n/2⌉ − 2.
Formulas
Comparisons
bubble/selection n(n − 1)/2; insertion: n − 1 (best) to n(n − 1)/2; merge ≈ n log₂ n − n + 1 (worst)
Inversions
insertion-sort shifts = number of inversions; reversed array has n(n − 1)/2
Quick sort
average / best 2T(n/2) + n → Θ(n log n); worst T(n − 1) + n → Θ(n²)
Lower bound
decision tree height ≥ ⌈log₂ n!⌉ = Ω(n log n)
Binary search
worst case ⌊log₂ n⌋ + 1 comparisons; min and max together: ⌈3n/2⌉ − 2
Counting sort / radix
Θ(n + k); radix Θ(d(n + k))
What GATE asks
- ★★★Worst / best / average case time of a sort. Which sort is Θ(n²) on sorted input; which is Θ(n log n) always.
- ★★★Number of swaps or comparisons on a given input. Run insertion, bubble or selection sort by hand, or count inversions.
- ★★★Quick sort partition / recurrence. Array after one partition, or the recurrence when the split is 1 : 9 or n/10 : 9n/10.
- ★★★Stable / in-place / space properties. Pick the algorithm that satisfies a property.
- ★★★Binary search and min-max problems. Number of probes, or minimum comparisons to find min and max.
Traps
Quick sort is Θ(n²) on already sorted input when the pivot is first or last.
Merge sort needs O(n) extra space; heap sort needs none; both are Θ(n log n).
Selection sort does few swaps but not few comparisons.
The Ω(n log n) bound applies only to comparison sorts: counting sort beats it.
The largest algorithm topic: traversals, MST, shortest paths and topological order are asked in several questions per paper.
- Graph representations and basic facts. An adjacency matrix uses Θ(V²) space with O(1) edge test; an adjacency list uses Θ(V + E) with O(degree) edge test. Sum of degrees = 2E. A simple undirected graph has at most V(V − 1)/2 edges; a connected one has at least V − 1; a tree has exactly V − 1 and no cycle. A simple directed graph has at most V(V − 1) edges.→ Σ deg = 2E; max edges V(V − 1)/2; tree = V − 1 edges.
- Breadth-first search. BFS uses a queue and explores vertices level by level. Time O(V + E) with lists (O(V²) with a matrix). The BFS tree gives shortest paths in an unweighted graph. Uses: shortest hop count, connected components, testing bipartiteness (2-colour by level), finding the shortest cycle.→ BFS: queue, O(V + E), shortest unweighted paths.
- Depth-first search and edge types. DFS uses recursion (a stack) and records discovery d[v] and finish f[v] times. Time O(V + E). Edge classes in a directed graph: tree, back, forward, cross. A directed graph has a cycle iff DFS finds a back edge. In an undirected graph every non-tree edge is a back edge. Articulation points and bridges come from low-link values.→ DFS: back edge ⇔ cycle; O(V + E).
- Topological sort and strongly connected components. A topological order lists the vertices of a DAG so every edge goes forward. Methods: repeatedly remove in-degree 0 vertices (Kahn), or reverse the DFS finish order. O(V + E). A DAG can have many orders; a unique order exists iff there is a Hamiltonian path. SCCs are found in O(V + E) by Kosaraju (DFS, transpose, DFS) or Tarjan; contracting them yields a DAG.→ Topological order ⇔ DAG; O(V + E).
- Minimum spanning trees. An MST connects all V vertices with V − 1 edges of least total weight. Kruskal: sort edges, add each edge that does not form a cycle (union-find), O(E log E). Prim: grow one tree by adding the cheapest edge leaving it, O(E log V) with a binary heap, O(V²) with an array. The cut property: the lightest edge crossing any cut is in some MST. If all edge weights are distinct the MST is unique.→ MST: V − 1 edges; Kruskal O(E log E); Prim O(E log V); distinct weights → unique.
- Single-source shortest paths. Dijkstra repeatedly finalises the closest unvisited vertex; it needs non-negative weights; O((V + E) log V) with a heap, O(V²) with an array. Bellman-Ford relaxes every edge V − 1 times: O(VE), works with negative edges and detects negative cycles. For a DAG, relax in topological order: O(V + E). BFS suffices for unit weights.→ Dijkstra: non-negative weights only; Bellman-Ford O(VE).
- All-pairs shortest paths and reachability. Floyd-Warshall: d[i][j] = min(d[i][j], d[i][k] + d[k][j]) for k = 1..V, three nested loops, Θ(V³), handles negative edges but not negative cycles. Running Dijkstra from every vertex costs O(V(V + E) log V). The same triple loop with OR and AND computes the transitive closure (Warshall).→ All-pairs: Floyd-Warshall Θ(V³), handles negative edges, not negative cycles.
Formulas
Edges
undirected simple: 0 ≤ E ≤ V(V − 1)/2; connected: E ≥ V − 1; directed simple: E ≤ V(V − 1); Σ deg = 2E
BFS / DFS
O(V + E) with adjacency lists; O(V²) with an adjacency matrix
MST
Kruskal O(E log E); Prim O(E log V) heap, O(V²) array; MST has V − 1 edges
Shortest paths
Dijkstra O((V + E) log V); Bellman-Ford O(VE); Floyd-Warshall Θ(V³)
Topological sort
O(V + E); exists iff the graph is a DAG
Edge classes (directed DFS)
back edge ⇔ cycle; forward / cross edges go to a finished vertex
What GATE asks
- ★★★Minimum spanning tree: weight, uniqueness, which edges. Run Kruskal by hand; decide whether the MST is unique, whether a given edge must be in it.
- ★★★Dijkstra / shortest path order or distance. Order in which vertices are finalised, and the final distance of a vertex; effect of negative edges.
- ★★★BFS / DFS order, time complexity, applications. Visit order for a given graph, finishing times, cycle detection.
- ★★★Topological orders of a DAG. Count or list valid orders, find which sequence is valid.
- ★★★Graph facts (degrees, edges, connectivity). Maximum edges, number of components, handshake lemma.
Traps
Dijkstra can fail with a negative edge even when there is no negative cycle.
Equal edge weights can give several different MSTs, but all have the same total weight.
Time depends on the representation: matrix BFS is O(V²), not O(V + E).
DFS in an undirected graph: an edge to the parent is not a back edge.
Identify the paradigm, write the recurrence, and fill a DP table by hand: these questions carry 2 marks each.
- Divide and conquer. Split into subproblems, solve recursively, combine. Cost comes from the recurrence T(n) = aT(n/b) + f(n). Examples: merge sort, quick sort, binary search, max and min in 3n/2 − 2 comparisons, Strassen (7 multiplications, Θ(n^2.81)), Karatsuba (3 multiplications, Θ(n^1.585)), closest pair in Θ(n log n), fast exponentiation in O(log n) multiplications.→ D&C cost = recurrence; know Strassen n^2.81 and Karatsuba n^1.585.
- Greedy algorithms. Make the locally best choice and never reconsider. Works when the problem has the greedy-choice property and optimal substructure. Examples: activity selection (sort by finish time), fractional knapsack (by value/weight), Kruskal, Prim, Dijkstra, Huffman coding, job sequencing with deadlines. Greedy fails for 0/1 knapsack and for coin change with unusual denominations.→ Greedy works for fractional knapsack, MST, Dijkstra, Huffman; fails for 0/1 knapsack.
- Huffman coding. Build an optimal prefix code: repeatedly merge the two least frequent nodes. n symbols need n − 1 merges; O(n log n) with a min-heap. Frequent symbols get short codes. The total cost is Σ frequency × code length, which equals the sum of all internal-node weights. No code is a prefix of another, so decoding is unambiguous.→ Huffman: n − 1 merges, O(n log n), no code is a prefix of another.
- Dynamic programming basics. Use DP when subproblems overlap and the problem has optimal substructure. Memoisation is top-down recursion with a cache; tabulation fills a table bottom-up. Plain recursive Fibonacci is exponential (about 1.618ⁿ calls), DP makes it O(n). Time = (number of states) × (work per state).→ DP = overlapping subproblems + optimal substructure; cost = cells × work per cell.
- Classic DP: LCS, edit distance, LIS. LCS of X (length m) and Y (length n): c[i][j] = c[i − 1][j − 1] + 1 if the symbols match, else max(c[i − 1][j], c[i][j − 1]); time and table size O(mn). Edit distance takes the min of insert, delete, replace. LIS is O(n²) with a simple DP or O(n log n) with binary search. Rod cutting, coin change and subset-sum follow the same pattern.→ LCS / edit distance: O(mn) time and table size.
- 0/1 knapsack and matrix-chain multiplication. 0/1 knapsack: t[i][c] = max(t[i − 1][c], t[i − 1][c − wᵢ] + vᵢ), O(nW) time, which is pseudo-polynomial (not polynomial in the input size). Matrix chain: m[i][j] = min over k of m[i][k] + m[k + 1][j] + p[i − 1]·p[k]·p[j], O(n³) time and O(n²) space. The order of multiplication changes the cost, not the result.→ Knapsack O(nW); matrix chain O(n³) time, O(n²) space.
Formulas
Divide & conquer examples
merge sort 2T(n/2) + n; binary search T(n/2) + 1; Strassen 7T(n/2) + n²; Karatsuba 3T(n/2) + n
Greedy
activity selection: sort by earliest finish; fractional knapsack: sort by v/w; Huffman: n − 1 merges
LCS / edit distance
time and space O(mn); c[i][j] = c[i − 1][j − 1] + 1 (match) else max(up, left)
0/1 knapsack
t[i][c] = max(t[i − 1][c], t[i − 1][c − wᵢ] + vᵢ); O(nW)
Matrix chain
m[i][j] = min_k ( m[i][k] + m[k + 1][j] + p[i − 1]p[k]p[j] ); O(n³) time, O(n²) space; (p × q)(q × r) costs pqr
Catalan (parenthesisations)
number of ways to parenthesise n matrices = C(n − 1)
What GATE asks
- ★★★Which paradigm solves it / which problem is greedy-solvable. Greedy vs DP vs divide and conquer; 0/1 knapsack needs DP.
- ★★★DP table value (LCS, knapsack, matrix chain, coin change). Fill a small table and read one cell or the final answer.
- ★★★Time or space complexity of a DP / recurrence. Number of states times work per state.
- ★★★Huffman code lengths or total bits. Run the merge procedure, then compute Σ f × length.
- ★★★Recursive algorithm analysis (Fibonacci, max-min, power). Number of calls or comparisons.
Traps
Greedy for 0/1 knapsack is wrong; greedy for fractional knapsack is right.
LCS needs O(mn) space for the full table, but only two rows if you need only the length.
Matrix chain minimises the number of scalar multiplications, and the dimension array has n + 1 entries for n matrices.
O(nW) is pseudo-polynomial: W can be exponential in its bit length.
5. 🧮 P, NP & NP-Completeness
Low ●Usually one conceptual question: which statements about P, NP, NP-hard and NP-complete are true.
- P, NP, NP-hard and NP-complete. P: solvable in polynomial time. NP: a proposed solution (certificate) can be verified in polynomial time. P ⊆ NP; whether P = NP is open. NP-hard: at least as hard as every problem in NP (need not be in NP). NP-complete: in NP and NP-hard. If any NP-complete problem is in P then P = NP.→ P ⊆ NP; NP-complete = in NP and NP-hard; certificate checking is the NP test.
- Reductions and classic NP-complete problems. A polynomial-time reduction A ≤ₚ B converts instances of A into instances of B. To prove B is NP-hard, reduce a known NP-hard problem to B (the direction matters). The first NP-complete problem is SAT (Cook-Levin). Chain: SAT → 3-SAT → Clique / Independent Set / Vertex Cover → Hamiltonian Cycle → TSP (decision), Subset Sum, 3-Colouring.→ Reduce the known hard problem TO the new one.
- Easy versus hard variants. Small changes flip the class: 2-SAT is in P, 3-SAT is NP-complete; 2-colouring is in P, 3-colouring is NP-complete; shortest path is in P, longest simple path is NP-hard; MST is in P, TSP is NP-hard; Eulerian circuit is in P, Hamiltonian cycle is NP-complete; matching is in P, 3-dimensional matching is NP-complete. Knapsack is NP-complete but has a pseudo-polynomial DP.→ 2-SAT, Euler, MST, shortest path are easy; 3-SAT, Hamiltonian, TSP, longest path are hard.
Formulas
Inclusions
P ⊆ NP; NP-complete = NP ∩ NP-hard; if P ≠ NP, then P ∩ NP-complete = ∅
Reduction direction
A ≤ₚ B and B ∈ P ⇒ A ∈ P; A NP-hard and A ≤ₚ B ⇒ B NP-hard
Classic chain
SAT → 3-SAT → Clique ↔ Independent set ↔ Vertex cover; Hamiltonian cycle → TSP
Pairs that differ
2-SAT ∈ P vs 3-SAT NPC; Euler circuit ∈ P vs Hamiltonian NPC; shortest vs longest simple path
What GATE asks
- ★★★Which statements about P / NP / NP-complete are true. Inclusion relations and consequences of P = NP; NP-hard problems that are not in NP.
- ★★★Reduction direction. If problem A reduces to B, what do you learn about A or B?
- ★★★Known NP-complete or polynomial problems. Pick the NP-complete problem from a list (2-SAT, Hamiltonian cycle, shortest path, MST).
Traps
NP stands for non-deterministic polynomial, not "not polynomial".
NP-hard problems need not be in NP (the halting problem is NP-hard).
To show B is hard you reduce a known hard problem to B, not B to it.
"Easy to verify" does not mean "easy to solve".