GATE CS 1995 Q2.22 — Linked Lists

Let us analyze each statement individually:

• Statement I: As the number of entries in a hash table increases, the number of collisions increases. (True)
  As more elements are inserted into a hash table of a fixed size, the load factor ($\alpha = n/m$) increases, which directly increases the probability of hash collisions.
• Statement II: Recursive programs are efficient. (False)
  Recursive programs incur overhead due to repeated function calls and stack frame allocations. In many cases, they are less space- and time-efficient than their iterative counterparts unless optimized (e.g., via tail-call optimization or memoization).
• Statement III: The worst case complexity for Quicksort is $O(n^2)$. (True)
  The worst-case time complexity of Quicksort is indeed $O(n^2)$, which occurs when the pivot consistently partitions the array into highly unbalanced sub-arrays (for example, when the input is already sorted and the first or last element is chosen as the pivot).
• Statement IV: Binary search using a linear linked list is efficient. (False)
  Binary search relies on $O(1)$ random access to locate the middle element. Since a linear linked list only supports sequential access, finding the middle element takes $O(n)$ time, resulting in an overall complexity of $O(n)$, which is not efficient.

Thus, only statements I and III are true, which corresponds to option D.