The GATE Grind

GATE 2021 CS – Question 12

Algorithms · Divide-and-Conquer · 1 mark · Multiple choice

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?

  1. $t > 2n-2$
  2. $t > 3\lceil \frac{n}{2} \rceil$ and $t \le 2n-2$
  3. $t > n$ and $t \le 3\lceil \frac{n}{2} \rceil$
  4. $t > \lceil \log_2(n) \rceil$ and $t \le n$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $t > n$ and $t \le 3\lceil \frac{n}{2} \rceil$

Explanation

The pairwise method needs about $3\lceil n/2\rceil - 2$ comparisons, which is optimal. This lies above $n$ and at most $3\lceil n/2\rceil$.