GATE CSE Algorithms Formula Sheet: Recurrences, Sorting, Graphs, DP

Algorithms questions in GATE CSE keep reusing a short list of results, from the Master theorem to Catalan numbers. This sheet collects them group by group. Each group has a table, one worked example of my own with the arithmetic shown, and the trap that costs marks.

For which topics past papers have asked most, read the Algorithms important topics guide; for the other subjects, use the GATE CSE formula sheet.

Key takeaways

• The Master theorem compares $f(n)$ with $n^{\log_b a}$; Case 3 also needs the regularity condition.
• Merge sort is stable but not in place; quicksort and heapsort are in place but not stable.
• Linear probing degrades much faster than chaining as the load factor $\alpha$ approaches 1.
• Build-heap is $\Theta(n)$, not $\Theta(n \log n)$, because most nodes sit near the bottom.
• Graph algorithm complexity depends on the data structure: an array suits dense graphs, a heap suits sparse ones.
• Catalan numbers count BSTs, binary tree shapes and stack permutations; $K_n$ has $n^{n-2}$ spanning trees.

The terms this sheet uses

• $n$ is the input size. For graphs, $V$ is the number of vertices and $E$ the number of edges.
• The load factor $\alpha = n/m$ is the number of keys $n$ stored in a hash table of $m$ slots.
• A probe is one slot examined during a hash search or insertion.
• A sort is stable if equal keys keep their input order, and in place if it uses only $O(1)$ extra space beyond the input.
• Heap height counts edges, so a single node has height 0.

Logs are base 2 unless a base is written.

Asymptotic notation: five symbols and how they combine

Each symbol is a comparison between two growth rates, valid from some $n_0$ onwards.

The growth order to carry into the hall is:

Worked example. Order $n^{10}$, $n^{\log n}$ and $2^{\sqrt{n}}$. Take the log of each: $10 \log n$, $(\log n)^2$ and $\sqrt{n}$. At $n = 2^{20}$ these are 200, 400 and 1024, and each gap keeps widening. So $n^{10} = o(n^{\log n})$ and $n^{\log n} = o(2^{\sqrt{n}})$.

The trap: $f = O(g)$ does not give $2^{f} = O(2^{g})$. Take $f = 2n$ and $g = n$; the ratio $2^{2n}/2^{n} = 2^{n}$ grows without bound.

Recurrences: the Master theorem in one table

A divide-and-conquer algorithm makes $a$ calls on inputs of size $n/b$ and spends $f(n)$ splitting and combining:

Here $a \ge 1$, $b > 1$, and $n^{c}$ is the work at the leaves.

The regularity condition in Case 3 says the work shrinks by a fixed factor at each level down, so the root's cost dominates the whole tree.

Worked example. One Case 2 and one Case 3, with $\displaystyle d = \tfrac{1}{2}$:

Trap: The gap must be polynomial. $2T(n/2) + n \log n$ is Case 2 with $k = 1$, giving $\Theta(n \log^2 n)$. $2T(n/2) + n/\log n$ sits at $k = -1$ and gives $\Theta(n \log \log n)$, not $\Theta(n)$.

Recursion trees and the recurrences worth memorising

When the split is unequal, add the cost level by level instead. If the level sums shrink geometrically, the top level dominates. If they stay equal, multiply one level by the depth. If they grow, the leaves dominate.

Worked example. For $T(n) = T(n/2) + T(n/4) + n$, the level sums are $n$, $\displaystyle \tfrac{3}{4}n$, $\displaystyle \tfrac{9}{16}n$, and so on:

These solutions come up often enough to learn by heart:

The trap: two calls on $n - 1$ double the work at every level, so $2T(n-1) + 1$ is exponential, not linear. The recurrence relations guide covers substitution and change of variable in full.

Sorting: complexity and properties in one table

Insertion sort makes inversions $+ (n - 1)$ comparisons, minus one for each key that moves to the front. Selection sort always makes $n(n-1)/2$ comparisons and at most $n - 1$ swaps. Any comparison sort needs $\lceil \log_2 n! \rceil$ comparisons in the worst case.

Worked example. Insertion sort on $[3, 1, 2, 5, 4]$. The inversions are $(3,1)$, $(3,2)$ and $(5,4)$, so there are 3. Only the key 1 moves to the front. The count is $3 + 4 - 1 = 6$ comparisons. The comparison lower bound, $\lceil \log_2 120 \rceil = 7$, applies to the worst input, not this one.

The trap: quicksort with a first-element pivot hits its $\Theta(n^{2})$ worst case on already sorted input.

Searching and hashing: load factor and expected probes

Binary search on a sorted array makes at most $\lfloor \log_2 n \rfloor + 1$ comparisons.

Worked example. At $\alpha = 0.75$, chaining needs 1.75 probes for an unsuccessful search and 1.375 for a successful one. Linear probing needs 8.5 and 2.5. Uniform hashing needs 4 and about 1.85. Primary clustering explains the gap.

Remember: GATE counts the empty slot where a search stops as a probe. Binary search on a linked list is $O(n)$, because reaching the middle element is itself a walk.

Heaps: height, index arithmetic and linear build-heap

Build-heap is linear because at most $\lceil n/2^{h+1} \rceil$ nodes have height $h$, and each costs $O(h)$:

Worked example. A heap of 20 nodes has height $\lfloor \log_2 20 \rfloor = 4$. Nodes 11 to 20 are its 10 leaves, so build-heap starts sifting down at node 10. For 5 distinct keys the left subtree holds 3 nodes and the right 1, so $H(5) = \binom{4}{3} \times 2 \times 1 = 8$ max-heaps.

The trap: applying the 1-based parent formula to a 0-based array.

The book's last-minute revision sheet adds step-by-step procedures for Dijkstra, Kruskal, Prim, BFS, DFS, build-heap and partition, with what GATE asks about each, plus a traps table. It is part of the GATE CSE 2027 book.

Graph algorithms: complexity depends on the data structure

Worked example. Take $V = 1000$, so $\log_2 V \approx 9.97$. With $E = 5000$, the array version of Dijkstra costs about $V^{2} = 10^{6}$ steps, and the heap version about $6000 \times 9.97 \approx 6 \times 10^{4}$. In the complete graph, $E = 1000 \times 999/2 = 499{,}500$, and the heap version costs about $5 \times 10^{6}$, so the array wins.

Trap: Adding a constant to every edge weight keeps the MST but can change shortest paths, because a path with more edges gains more. Multiplying every weight by a positive constant changes neither.

Dynamic programming: three recurrences and their tables

In the matrix chain row, matrix $A_i$ has dimensions $p_{i-1} \times p_i$. The knapsack's second option applies only when $w_i \le w$.

Worked example. Take $A$ as $4 \times 10$, $B$ as $10 \times 3$ and $C$ as $3 \times 12$, so $p = (4, 10, 3, 12)$:

The minimum is 264 scalar multiplications.

The trap: $n$ matrices have $C_{n-1}$ parenthesisations, not $C_n$, so three matrices have $C_2 = 2$.

Greedy: Huffman coding and activity selection

Worked example. Frequencies a: 2, b: 3, c: 5, d: 7, e: 13, total 30. The merges are $2 + 3 = 5$, $5 + 5 = 10$, $7 + 10 = 17$ and $13 + 17 = 30$. Code lengths are e 1, d 2, c 3, a 4, b 4, so the total is:

The merge weights $5 + 10 + 17 + 30$ give the same 62. A fixed 3-bit code needs 90.

The trap: tie-breaking can change one symbol's code length but never the total bits.

Counting formulas: Catalan numbers and spanning trees

Worked example. Check $4^{2} = 16$ for $K_4$ by hand. It has 6 edges, so $\binom{6}{3} = 20$ three-edge subsets. Three edges on four vertices fail to be a tree only when they form a triangle, and $K_4$ has $\binom{4}{3} = 4$ triangles. That leaves $20 - 4 = 16$.

In one line: $n^{n-2}$ counts labelled spanning trees, distinct edge sets on named vertices, not tree shapes.

The graph theory questions guide covers the rest of the counting family, and the time complexity questions guide turns these bounds into loop-counting practice.

Quick revision

1. Master theorem: compare $f(n)$ with $n^{\log_b a}$; Case 2 adds one log; Case 3 needs $a\,f(n/b) \le d\,f(n)$, $d < 1$.
2. $2T(n/2) + n \log n = \Theta(n \log^2 n)$; $2T(n-1) + 1 = \Theta(2^{n})$; $T(\sqrt{n}) + 1 = \Theta(\log \log n)$.
3. Stable: insertion, bubble, merge, counting, radix. Not in place: merge, counting, radix.
4. Chaining $1 + \alpha$; linear probing $\displaystyle \frac{1}{2}(1 + 1/(1 - \alpha)^{2})$ unsuccessful; count the empty slot.
5. Heap height $\lfloor \log_2 n \rfloor$, $\lceil n/2 \rceil$ leaves, build-heap $\Theta(n)$.
6. Dijkstra $O(V^{2})$ array or $O((V + E) \log V)$ heap; Bellman–Ford $O(VE)$; Floyd–Warshall $\Theta(V^{3})$.
7. LCS $\Theta(mn)$, knapsack $\Theta(nW)$, matrix chain $\Theta(n^{3})$ with $C_{n-1}$ parenthesisations.
8. Huffman total bits $= \sum f_i \ell_i =$ sum of merge weights; $K_n$ has $n^{n-2}$ spanning trees.