GATE CS 2021 Set 1 Q2 — Arrays, Stacks and Queues

To find both the minimum and maximum elements in an arbitrary array of size $n$, we can use an optimal pairwise comparison algorithm:

1. If $n$ is odd, initialize both min and max to the first element. If $n$ is even, compare the first two elements, set min to the smaller one and max to the larger one.
2. Process the remaining elements in pairs. For each pair, compare the two elements with each other, then compare the smaller element with min and the larger element with max.

The total number of comparisons, $t$, required by this optimal algorithm is:

• If $n$ is even: $$\frac{3n}{2} - 2 \text{ comparisons}$$ (1 comparison for the first pair, and $3 \times \left(\frac{n-2}{2}\right)$ comparisons for the remaining pairs).
• If $n$ is odd: $$\frac{3(n-1)}{2} \text{ comparisons}$$ ($3 \times \frac{n-1}{2}$ comparisons for the pairs).

We can write this compactly as:

Let us analyze the bounds for $t$ when $n \ge 5$:

• Since $t \approx 1.5n - 2$, we have $t > n$ for all $n \ge 5$.
• Comparing with $3\lceil \frac{n}{2}\rceil$:
  • For even $n$: $t = 1.5n - 2 < 1.5n = 3\lceil \frac{n}{2}\rceil$.
  • For odd $n$: $t = 1.5(n-1) < 1.5(n+1) = 3\lceil \frac{n}{2}\rceil$.
  Thus, $t \le 3\lceil \frac{n}{2}\rceil$ holds true.

Therefore, the correct choice is C: $t > n \text{ and } t \le 3\lceil \frac{n}{2}\rceil$.