Home › Previous year questions › GATE 2021 CS (CS1) › Question 12GATE 2021 CS (CS1) – 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?
$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$ 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$.
More Divide-and-Conquer questions GATE 2019 CS Q35 – Consider a sequence of 14 elements: A=[-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3,0]. The… GATE 2014 CS (CS2) Q23 – Which gives the solution of T(n)=2T(n/2)+ n, T(1) = 1? GATE 2015 CS (CS2) Q49 – partition(a,n) uses a[0] as pivot, moves values ≤pivot left and greater values right, and… GATE 2015 CS (CS3) Q63 – Find DOSOMETHING(c,a,n) for k=4,c=(1,0,1,1),a=2,n=8. GATE 2009 CS Q39 – Quicksort chooses the (n/4)th smallest element as pivot for n elements using an O(n)-time… GATE 2008 CS Q43 – Quicksort has a pivot routine splitting every list so each side contains at least… All Divide-and-Conquer questions →