GATE CS 1998 Q1.22 — Searching, Sorting, Hashing

We can determine the correct matching by analyzing the worst-case time complexity of each algorithm:

• Binary Search (R): A search algorithm on a sorted array that halves the search space at each step. Its time complexity is governed by the recurrence $T(n) = T(n/2) + O(1)$, which yields $O(\log n)$.
  $$\text{Matching: A } \rightarrow \text{ R}$$
• Selection (P): The selection problem (finding the $k$-th smallest element in an unsorted array of size $n$) can be solved in linear time $O(n)$ using the Median-of-Medians algorithm (or QuickSelect on average).
  $$\text{Matching: B } \rightarrow \text{ P}$$
• Merge Sort (S): A divide-and-conquer sorting algorithm with the recurrence $T(n) = 2T(n/2) + O(n)$. Its worst-case, average-case, and best-case time complexity is $O(n \log n)$.
  $$\text{Matching: C } \rightarrow \text{ S}$$
• Insertion Sort (Q): A comparison-based sorting algorithm. In the worst case (e.g., when the input array is sorted in reverse order), it requires $O(n^2)$ comparisons and shifts.
  $$\text{Matching: D } \rightarrow \text{ Q}$$

Combining these matches, we get: A-R, B-P, C-S, D-Q, which corresponds to Option B.