GATE CSE 2021 Set 1 | Question: 2

Question

• A.
• B.
• C.
• D.

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?

• A. $t>2n-2$
• B. $t>3\lceil \frac{n}{2}\rceil \text{ and } t\leq 2n-2$
• C. $t>n \text{ and } t\leq 3\lceil \frac{n}{2}\rceil$
• D. $t>\lceil \log_2(n)\rceil \text{ and } t\leq n$

Comments

Similar questions:

https://gateoverflow.in/1248/gate-cse-2007-question-50

https://gateoverflow.in/1917/gate-cse-2014-set-1-question-39

Answer 1

The Answer is B. It will take 3n/2 comparisons by divide and conquer, and it will take 2n-2 without D&C.

Answer 2

For Normal min max problem it will take

2n-2 Worst case

n-1 Best case

 

For Divide and conquer we can use tournament tactic and get the answer in 3n/2 comparisions

As the lowest upper bound is asked the answer will be 

C t>n and t<=3|n/2|

Comments

I think here no. of comparisons need to be considered rather than bounds. So, as you said “2n-2 Worst case”

So answer should be t>n and t<=2n-2 in my opinion.

Please correct me if wrong!

---

I might be wrong but according to ME key it is t>3n/2 and T<2n-2

---

@Arjun please check

Answer 3

I believe the answer will be B

lowest upper bound has been asked we need n-1 comparisons in the best case but 2n-2 comparisons in the worst case

similarly if we use divide and conquer method we will get 3(n/2)-2 comparisons in all the cases

as the method is not specified so we have to consider both the worst case comparisons

so it will be between 3(n/2) and 2n-2...i am quite sure for this one correct me if i am wrong

Answer 4

C)
Tournament Method:

• Imagine using merge-sort and you’d divided the array elements in pairs of two, every element is compared with each other.
• The largest(or smallest if preferred) is selected out of the two and the winners are copied to a new array and the procedure it repeated till we have one element remaining.
   

For this,
At first we need $\frac{n}{2}$ comparisons(since $\frac{n}{2}$ pairs), then $\frac{n}{4}$, so on this sums to $n$ using AP.
 

• For find ingthe smallest elements we would’ve losers left out in the first round $\frac{n}{2}$ losers to be precise.
• We again use this procedure instead for finding smaller amongst all.

For this,
At first we need $\frac{n}{4}$(since we are pitting losers against losers) comparisons, then $\frac{n}{8}$ so on which sum to $\frac{n}{2}$.

 

So, we know that the upper bound is $\frac{3n}{2}$(adding up) and will be equal to it. Hence C is the answer.

Another more intuitive way to understand this is the build heap operation.