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 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 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 \ 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 n) of Quick sort with its worst-case time (n2) Off-by-one errors when counting possible outcomes for binary search (e.g., using 2(n) instead of 2(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

Searching, Sorting and Hashing

27 Qs · since 2012 · 39 marks · 1.6 marks/paperMedium yield

Take topic test

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 si… Guide

Type

GATE CSE 2026 Set 1Q24MSQ1 markEasyConsider a hash table $P[0, 1, \dots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is $h(x) = (x + 7) \bmod 11$ . Consider the following sequence of insertions performed on $P$ : $1, 13, 22, 15, 11, 24$ Which of the following…
GATE CSE 2026 Set 2Q30NAT1 markEasyThe keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the hash function $h(k) = k \bmod 9$ . The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is _______. (answer in integer)
GATE CSE 2026 Set 2Q32NAT1 markMediumConsider an array $A = [10, 7, 8, 19, 41, 35, 25, 31]$ . Suppose the merge sort algorithm is executed on array $A$ to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations. A merge operation on sorted left array $L$ and sorted right array $R$ is said to be void if…
GATE CSE 2025 Set 1Q65NAT2 marksMediumIn a double hashing scheme, $h_1(k) = k \bmod 11$ and $h_2(k) = 1 + (k \bmod 7)$ are the auxiliary hash functions. The size $m$ of the hash table is 11. The hash function for the $i$ -th probe in the open address table is $[h_1(k) + i\ h_2(k)] \bmod m$ . The following keys are inserted in the given order: 63,…
GATE CSE 2025 Set 2Q41MCQ2 marksMediumAn array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1 \le i \le n$ such that $A[1 \dots i]$ is sorted in the non-decreasing order and $A[i + 1 \dots n]$ is sorted in the non-increasing order. Which ONE of the following represents the best possible asymptotic bound…
GATE CSE 2023Q20MCQ1 markEasyAn algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash table, and $k > m$ . Which one of the following is the best hashing strategy to…
GATE CSE 2022Q16MCQ1 markEasySuppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_1$ and $h_2$ . Further suppose our hashing scheme uses $h_1$ for the odd keys and $h_2$ for the even keys. What is the expected number of keys in a slot?
GATE CSE 2021 Set 1Q2MCQ1 markMediumLet P be an array containing $n$ integers. Let $t$ be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of $n$ elements. Which one of the following choices is correct?
GATE CSE 2021 Set 1Q47MSQ2 marksMediumDiagramConsider a *dynamic* hashing approach for 4-bit integer keys: 1. There is a main hash table of size 4. 2. The 2 least significant bits of a key is used to index into the main hash table. 3. Initially, the main hash table entries are empty. 4. Thereafter, when more keys are hashed into it, to resolve collisions, the…
GATE CSE 2021 Set 2Q8MCQ1 markEasyWhat is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$ ?
GATE CSE 2020Q23NAT1 markEasyConsider a double hashing scheme in which the primary hash function is $h_1(k) = k \bmod 23$ , and the secondary hash function is $h_2(k) = 1 + (k \bmod 19)$ . Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value…
GATE CSE 2019Q20NAT1 markEasyAn array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _______.
GATE CSE 2017 Set 1Q48NAT2 marksMediumLet $A$ be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's. The problem is to find the smallest index $i$ such that $A[i]$ is 1 by probing the minimum number of locations in $A$ . The worst case number of probes performed by an optimal algorithm is ________.
GATE CSE 2016 Set 1Q13MCQ1 markEasyThe worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
GATE CSE 2016 Set 2Q13MCQ1 markMediumAssume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE? I. Quicksort runs in $\Theta(n^2)$ time II. Bubblesort runs in $\Theta(n^2)$ time III. Mergesort runs in $\Theta(n)$ time IV. Insertion sort runs…
GATE CSE 2015 Set 1Q40MCQ2 marksMediumAn algorithm performs $(\log N)^{1/2}$ find operations, $N$ insert operations, $(\log N)^{1/2}$ delete operations, and $(\log N)^{1/2}$ decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted.…
GATE CSE 2015 Set 3Q17NAT1 markEasyGiven a hash table $T$ with 25 slots that stores 2000 elements, the load factor $\alpha$ for $T$ is _______.
GATE CSE 2014 Set 1Q14MCQ1 markMediumLet $P$ be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let $t_1$ and $t_2$ be the number of comparisons made by $P$ for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
GATE CSE 2014 Set 1Q39NAT2 marksEasyThe minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________.
GATE CSE 2014 Set 1Q40MCQ2 marksEasyConsider a hash table with 9 slots. The hash function is $h(k) = k \bmod 9$ . The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are
GATE CSE 2014 Set 2Q38NAT2 marksMediumSuppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is $\underline{\hspace{1cm}}$ .
GATE CSE 2014 Set 3Q14MCQ1 markEasyYou have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
GATE CSE 2014 Set 3Q38MCQ2 marksMediumConsider the decision problem $2CNFSAT$ defined as follows: $\Phi \mid \Phi$ is a satisfiable propositional formula in CNF with at most two literals per clause For example, $\Phi = (x_1 \vee x_2) \wedge (x_1 \vee \overline{x_3}) \wedge (x_2 \vee x_4)$ is a Boolean formula and it is in $2CNFSAT$ . The…
GATE CSE 2014 Set 3Q40MCQ2 marksEasyConsider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
GATE CSE 2013Q6MCQ1 markEasyWhich one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?
GATE CSE 2013Q30MCQ2 marksMediumThe number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is
GATE CSE 2012Q39MCQ2 marksMediumA list of $n$ strings, each of length $n$ , is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

Topic guide

What does GATE test in Searching, Sorting and Hashing?

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
common · mixed · 2 marks · 2021, 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
common · mixed · 1.5 marks · 2026, 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
common · mixed · 1 marks · 2019, 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
common · NAT · 1.5 marks · 2026, 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
occasional · MCQ · 2 marks · 2025, 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
rare · MCQ · 2 marks · 2015
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
common · NAT · 1 marks · 2020
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
common · MSQ · 1 marks · 2026
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
common · MCQ · 1.5 marks · 2022, 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
occasional · MCQ · 1 marks · 2023
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
common · MCQ · 1 marks · 2016
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
occasional · NAT · 2 marks · 2017
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
common · MCQ · 1 marks · 2021
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 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 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 \ 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 n) of Quick sort with its worst-case time (n2)
Off-by-one errors when counting possible outcomes for binary search (e.g., using 2(n) instead of 2(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).

Searching, Sorting and Hashing

27 Qs · since 2012 · 39 marks · 1.6 marks/paperMedium yield

Take topic test

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 si… Guide

Type

Topic guide

What does GATE test in Searching, Sorting and Hashing?

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
common · mixed · 2 marks · 2021, 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
common · mixed · 1.5 marks · 2026, 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
common · mixed · 1 marks · 2019, 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
common · NAT · 1.5 marks · 2026, 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
occasional · MCQ · 2 marks · 2025, 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
rare · MCQ · 2 marks · 2015
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
common · NAT · 1 marks · 2020
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
common · MSQ · 1 marks · 2026
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
common · MCQ · 1.5 marks · 2022, 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
occasional · MCQ · 1 marks · 2023
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
common · MCQ · 1 marks · 2016
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
occasional · NAT · 2 marks · 2017
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
common · MCQ · 1 marks · 2021
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 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 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 \ 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 n) of Quick sort with its worst-case time (n2)
Off-by-one errors when counting possible outcomes for binary search (e.g., using 2(n) instead of 2(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