GATE CS 2014 Set 1 Q39 — Searching, Sorting, Hashing

To find both the minimum and maximum of $n$ elements with the minimum number of comparisons, we use the optimal pairwise comparison algorithm.

• Case 1: $n$ is even
  • Compare the first two elements to initialize min and max. This takes $1$ comparison.
  • Process the remaining $n - 2$ elements in pairs. For each pair: compare the two elements with each other (1 comparison), compare the smaller element with the current min (1 comparison), and compare the larger element with the current max (1 comparison). This requires $3$ comparisons per pair.
  • Total comparisons = $1 + 3 \times \left(\frac{n - 2}{2}\right) = \frac{3n}{2} - 2$.
• Case 2: $n$ is odd
  • Initialize both min and max to the first element (0 comparisons).
  • Process the remaining $n - 1$ elements in pairs.
  • Total comparisons = $3 \times \left(\frac{n - 1}{2}\right) = \frac{3n - 3}{2}$.

Since $100$ is an even number, we use the formula for even $n$:

$$\text{Total comparisons} = \frac{3 \times 100}{2} - 2 = 150 - 2 = 148$$

Thus, the minimum number of comparisons required is 148.