What are common examiner traps in Searching, Sorting and Hashing?

Assuming picking the central or median-of-three pivot prevents worst-case (n2) behavior on all inputs (adversarial inputs still exist). Forgetting the -1 in pairwise array merging: merging lengths m and n costs at most m + n - 1 comparisons, not m + n. Mixing 0-indexed and 1-indexed hash tables during open addressing double hashing calculations. Applying O(n log n) string merge sort without multiplying by the O(n) string comparison cost. Forgetting that early-exit Bubblesort and standard Insertion sort take (n) time on already sorted inputs, while Merge sort remains (n log n). Zero-based vs one-based probe indexing: confusing probe 0 (initial hash) with probe 1 (first collision resolution step). Modulo wrap-around omission: forgetting to apply mod m when linear or double probing wraps past the end of the table array. Dependent vs independent probability errors: treating independent random hashing of keys as non-replacement sampling (m-1, m-2 vs constant m-s choices). Assuming partitioned hash functions alter expected load: partitioning keys between two distinct SUHA functions still yields n/m total expected keys per slot. Confusing average-case time (n log n) of Quick sort with its worst-case time (n2) Off-by-one errors when counting possible outcomes for binary search (e.g., using ⌈ log2(n) ⌉ instead of ⌈ log2(n+1) ⌉ when an element can also be absent or occur at position n+1) Confusing the number of recursive stack frames/operations with linear traversal when array slicing or mid-point arithmetic is involved

GATE CSE Searching, Sorting and Hashing PYQs

Medium yield21% of Algorithms

Across GATE CS exams, Searching, Sorting, and Hashing are tested with a strong emphasis on exact comparison/swap counts, worst/best-case edge cases (especially… Read the guide

Take topic test

Questions: 27
Asked: since 2012
Total marks: 39
Marks / paper: 1.6

27 GATE CSE Searching, Sorting and Hashing PYQs with solutions, from Algorithms. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Searching, Sorting and Hashing

Concepts, patterns, formulas and traps distilled from past papers.

Across GATE CS exams, Searching, Sorting, and Hashing are tested with a strong emphasis on exact comparison/swap counts, worst/best-case edge cases (especially for Quicksort and simultaneous min-max finding), trace-based simulation (such as step-by-step hashing probes and merge passes), and asymptotic tradeoffs for specialized or composite data inputs. Questions range from conceptual 1-mark classification to rigorous 2-mark NATs requiring precise manual execution of collision resolution or optimal merge trees.

Core concepts

Quicksort partition mechanics and worst-case permutations under various pivot rules
Pairwise simultaneous minimum and maximum finding algorithm
Optimal merge pattern using min-heap / greedy strategy
Chaining vs. Open Addressing (Linear Probing, Quadratic Probing, Double Hashing)
Hash table load factor and chain length distributions
Binary search modifications (bitonic peak finding and partitioned binary search)
Comparison cost on complex keys (e.g., variable or length-n strings)
Elementary sorting bounds (Selection sort swaps O(n), Insertion sort best case O(n))
Simple Uniform Hashing Assumption (SUHA) and independence of keys
Linear probing collision resolution and cyclic wrap-around
Double hashing probe formulas and non-zero step sizes (h2(k) 0)
Expected chain length / load factor = n/m
Universal hashing vs. deterministic hash functions against adversaries
Probability calculations on slot occupancy
Worst-case asymptotic running times of Insertion sort, Merge sort, and Quick sort
Decision tree lower bounds and information-theoretic probe limits
Binary search recurrence relations and arithmetic operation counting
Monotone array transition point search

Recurring question patterns

Simultaneous Min-Max Comparison Counting
Commonmixed2 marks2021, 2014
Determining the exact minimum comparisons or bounding intervals required to find both the minimum and maximum elements in an array of size $n$ using pairwise grouping.
Hash Table Collision Resolution Trace & Metric Computation
Commonmixed1.5 marks2026, 2025, 2021, 2015
Tracing the insertion of given integer keys into a hash table using chaining, dynamic bitwise trees, or open addressing (linear, quadratic, or double hashing) to find slot positions, chain lengths, or load factor $\alpha$ .
Quicksort Pivot Selection & Partition Behavior
Commonmixed1 marks2019, 2016, 2014
Analyzing comparisons, worst-case recurrences, or probability of bad partitions under various pivot selection rules (first element, central element, or uniformly random pivot) on specific input permutations.
Merge Sort Traces and Multi-way/Optimal Merging
CommonNAT1.5 marks2026, 2014
Calculating exact comparison counts using Huffman-like greedy 2-way merging (Optimal Merge Pattern) or step-by-step tracing of recursion trees and specific merge predicates (e.g., void merges).
Search/Sort Variations on Non-standard Inputs
OccasionalMCQ2 marks2025, 2013, 2012
Evaluating asymptotic bounds for searching in specialized structured arrays (e.g., bitonic arrays), sorting compound items (e.g., $n$ strings of length $n$ ), or inverse-solving element counts $k$ for fixed asymptotic time targets.
Operation-Frequency-Driven Data Structure Selection
RareMCQ2 marks2015
Choosing the data structure (unsorted array, min-heap, balanced BST) that minimizes total asymptotic time given a specific non-uniform frequency mix of operations.
Open Addressing Probe Address Calculation
CommonNAT1 marks2020
Given hash functions (e.g., $h_1(k)$ and $h_2(k)$ ) and a table size $m$ , calculate the exact slot index inspected at a specific probe number $i$ for a given key $k$ in open addressing schemes like double hashing or linear probing.
Hash Table Insertion Tracing & Occupancy
CommonMSQ1 marks2026
Given an initial empty table and a sequence of keys with a specified collision resolution method (e.g., linear probing with wrap-around modulo arithmetic), trace step-by-step insertions to identify occupied or unoccupied slot indices.
Probability and Expectation under SUHA
CommonMCQ1.5 marks2022, 2014
Evaluate the probability of specific slot configurations (e.g., specific slots remaining empty after multiple insertions) or calculate expected slot chain lengths / expected keys per slot using linearity of expectation under simple uniform hashing assumptions.
Theoretical Concepts & Adversarial Collision Resistance
OccasionalMCQ1 marks2023
Test understanding of hash function properties, limitations of deterministic hashing (division/multiplication methods) against worst-case adversaries, and the role of universal hashing in achieving $O(1)$ expected performance.
Standard Algorithm Worst-Case Comparison
CommonMCQ1 marks2016
Matching or listing the tight asymptotic worst-case time complexities $\Theta(\cdot)$ of classical sorting algorithms like Insertion sort, Merge sort, and Quick sort.
Binary Search Decision Tree and Worst-Case Probe Count
OccasionalNAT2 marks2017
Determining the exact minimum number of worst-case probes required by an optimal algorithm to locate a boundary or transition point in a sorted/monotone array of fixed size $n$ .
Recurrence and Operation Count for Recursive Searching
CommonMCQ1 marks2021
Identifying the asymptotic bound $\Theta(\cdot)$ on the number of arithmetic/comparison operations executed during recursive binary search.

Formulas GATE uses

Simultaneous Min and Max Comparisons (Even $n$)

\text{Comparisons} = 1 + \frac{3}{2}(n-2) = \frac{3n}{2} - 2

Used when finding both minimum and maximum of an even number of elements with minimum comparisons by pairwise grouping.

Simultaneous Min and Max Comparisons (Odd $n$)

\text{Comparisons} = \frac{3(n-1)}{2} = 3 \left\lfloor \frac{n}{2} \right\rfloor

Used when calculating optimal min-max comparisons for an odd number of elements.

Worst-case 2-Way Merge Comparisons

\text{Comparisons}(m, n) = m + n - 1

Used during each step of the optimal merge pattern when combining two sorted arrays of sizes $m$ and $n$ .

Load Factor of Hash Table

\alpha = \frac{n}{m}

Used to compute average items per slot where $n$ is the number of keys and $m$ is the number of slots.

Double Hashing Probe Sequence

h(k, i) = [h_1(k) + i \cdot h_2(k)] \bmod m

Used to determine the $i$ -th probe slot for key $k$ in open addressing double hashing.

Worst-case Quicksort Pivot Probability

P(\text{worst pivot}) = \frac{2}{n}

Used for uniform random pivot selection on $n$ distinct elements where minimum and maximum elements yield the most unbalanced split.

Linear Probing Probe Sequence

h(k, i) = (h(k) + i) \bmod m

Used when iteratively resolving collisions by inspecting consecutive cyclic slots.

Expected Slot Occupancy (Load Factor under SUHA)

E[X_j] = \sum_{i=1}^n E[I_i] = \frac{n}{m}

Used to find the expected number of keys hashing to any specific slot $j$ when $n$ independent keys are hashed across $m$ slots.

Independent Slot Avoidance Probability

P(\text{all } k \text{ keys avoid } s \text{ specific slots}) = \left(\frac{m - s}{m}\right)^k

Used under SUHA when independent keys must hash exclusively outside a designated subset of $s$ slots.

Binary Search Worst-Case Probe Bound

\text{Worst-case Probes} = \lceil \log_2(n + 1) \rceil

Used to find the minimum number of probes required in the worst case to determine the exact transition index in a sequence of $n$ elements with $n+1$ possible outcome states.

Recursive Binary Search Recurrence

T(n) = T(\lfloor n/2 \rfloor) + \Theta(1) = \Theta(\log_2 n)

Used when analyzing the number of operations or recursive steps executed by binary search on an array of size $n$ .

Worst-Case Unbalanced Quick Sort Recurrence

T(n) = T(n - 1) + \Theta(n) = \Theta(n^2)

Used to evaluate the worst-case running time of Quick sort under extreme unbalanced pivot partitions.

Examiner traps in Searching, Sorting and Hashing

Assuming picking the central or median-of-three pivot prevents worst-case (n2) behavior on all inputs (adversarial inputs still exist).
Forgetting the -1 in pairwise array merging: merging lengths m and n costs at most m + n - 1 comparisons, not m + n.
Mixing 0-indexed and 1-indexed hash tables during open addressing double hashing calculations.
Applying O(n log n) string merge sort without multiplying by the O(n) string comparison cost.
Forgetting that early-exit Bubblesort and standard Insertion sort take (n) time on already sorted inputs, while Merge sort remains (n log n).
Zero-based vs one-based probe indexing: confusing probe 0 (initial hash) with probe 1 (first collision resolution step).
Modulo wrap-around omission: forgetting to apply mod m when linear or double probing wraps past the end of the table array.
Dependent vs independent probability errors: treating independent random hashing of keys as non-replacement sampling (m-1, m-2 vs constant m-s choices).
Assuming partitioned hash functions alter expected load: partitioning keys between two distinct SUHA functions still yields n/m total expected keys per slot.
Confusing average-case time (n log n) of Quick sort with its worst-case time (n2)
Off-by-one errors when counting possible outcomes for binary search (e.g., using ⌈ log2(n) ⌉ instead of ⌈ log2(n+1) ⌉ when an element can also be absent or occur at position n+1)
Confusing the number of recursive stack frames/operations with linear traversal when array slicing or mid-point arithmetic is involved

How questions are asked

Trace and find the target slot in double hashing / open addressing
Calculate exact number of comparisons for simultaneous min-max or optimal merge
Count occurrences of a specific merge condition (e.g., void merges) during standard algorithm execution
Calculate chain metrics (maximum, minimum, average chain lengths) under modular hashing
Asymptotic complexity analysis with specialized data sizes or non-standard operation counts
Probability calculation for pivot placement under randomized algorithms
Probe address computation (evaluate h(k, i) numerically)
Insertion trace to identify empty/occupied table slots
Probability computation under Simple Uniform Hashing Assumption
Conceptual selection of hashing scheme against adversarial collision
Multi-algorithm complexity matching list (MCQ)
Exact worst-case probe calculation for array search (NAT)
Asymptotic operation count for recursive divide-and-conquer routines (MCQ)

Paper trends

Shift from standard Big-O identification of basic sorting algorithms towards exact manual tracing (e.g., counting void merges, computing exact probe index in double hashing).
2026, 2025
Increased usage of NAT question formats for hashing and merge computations rather than multiple-choice options.
2026, 2025, 2019, 2015, 2014
Inclusion of non-standard hashing mechanisms, such as MSQs testing trie-like dynamic bit-sliced collision resolution.
2021
Shift from purely single-choice probability or theory questions to procedural tracing and formula evaluation tested via NAT and MSQ formats.
2026, 2020, 2014
Consistent focus on 1-mark foundational conceptual checks, with occasional 2-mark probability/counting questions.
2026, 2023, 2022, 2020, 2014
Direct identification of standard sorting complexities was tested in 1-mark MCQs, while exact decision-tree lower bounds on fixed array sizes appeared as 2-mark NAT questions.
2017, 2016
Questions consistently target divide-and-conquer recurrences ( $T(n) = T(n/2) + O(1)$ and $T(n) = 2T(n/2) + O(n)$ ), emphasizing worst-case behavior across recursive search and sort algorithms.
2021, 2016

Difficulty notes

Easy questions test direct definitions (load factor $\alpha = n/m$ , maximum swaps in selection sort) or single-concept evaluation (chaining max length on <10 keys). Medium questions involve manual tracing (double hashing probe collisions, merge sort execution on 8 elements, optimal merge tree calculation) or multi-step comparison arithmetic ( $\{3n/2 - 2\}$ bounds, bitonic search multi-phase log analysis).