GATE CS 2021 Set 1 Q.12 (CS Q.2): Searching and Sorting Algorithms

Let $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?

$t > 2n - 2$

$t > 3\lceil \frac{n}{2} \rceil$ and $t \le 2n - 2$

$t > n$ and $t \le 3\lceil \frac{n}{2} \rceil$

$t > \lceil \log_2(n) \rceil$ and $t \le n$

Official answer and solution

Official answer: C
From: Official GATE 2021 answer key

Solution

Recall the optimal tournament/pairing comparison bounds for finding simultaneous minimum and maximum.

Finding the minimum alone in an arbitrary unsorted array of $n$ elements requires $n - 1$ comparisons. Finding both minimum and maximum simultaneously cannot be done in fewer than $\lceil \frac{3n}{2} \rceil - 2$ comparisons.

By pairing elements up initially (costing $\lfloor n/2 \rfloor$ comparisons) and then comparing winners for maximum and losers for minimum, the total number of comparisons is:

t = \begin{cases} \frac{3n}{2} - 2 & \text{if } n \text{ is even} \\ \frac{3(n-1)}{2} & \text{if } n \text{ is odd} \end{cases} = \left\lceil \frac{3n}{2} \right\rceil - 2

For any $n \ge 2$ , this optimal bound satisfies $t > n$ and $t \le 3\lceil n/2 \rceil$ , matching option C.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 12 of 65, printed as CS Q.2
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source