GATE CSE 2021 Set 1 | Question: 2

Question

​​​​​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

You’re a god sent angel for linking similar questions here @Shiva Sagar Rao

---

brilliant answer

---

Lowest Upper Bound means Smallest element in Upper Bound.

Let n=100.

No of Comparisions = 3(50) -2 = 148

We need  t >=148  and for Lowest Upper Bound ,it should be in close range to 148.

1. t>198
2. t>150 and t<=198
3. t>100 and t<=150
4. t>7 and t<=100

So d is discarded. a,b,c are all satisfied if we only take t>=148 into consideration.

for Lowest Upper Bound ,it should be in close range to 148 => (100,150] is much closer compared to (150,198]

So C is the answer

Let n=99

Comparisions  = 147 =>  t>=147

1. t>196
2. t>149 and t<=196
3. t>99 and  t<=149
4. t>7 and t<=99

Still  d is discarded. a,b,c are all satisfied if we only take t>=147 into consideration.

for Lowest Upper Bound ,it should be in close range to 148 => (99,149] is much closer compared to (149,196]

So C is the answer

 

Answer 1

Correct Option: C

---

The answer is a stub!

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 each pairs 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$ , an AP problem.

$\text{Comparisons Req. for finding the Max Element}=\cfrac{n}{2}+\cfrac{n}{4}+\cfrac{n}{8}...=n$

• For finding the smallest element we would use the losers left out in the first round $\frac{n}{2}$ losers to be precise.
• We again use this procedure with an intention for finding smaller amongst all, (worst losers will be the best winners in these rounds, ironical indeed).

For this,
We need, $\frac{n}{4}$ at first since we are pitting losers against losers comparisons then, $\frac{n}{8}$ so on which sums upto $\frac{n}{2}$.

$\text{Comparisons Req. for finding the Min Element}=\cfrac{n}{4}+\cfrac{n}{8}+\cfrac{n}{16}...=\cfrac{n}{2}$

$\text{Total Number of Comparisons Number Required}=n+\cfrac{n}{2}=\cfrac{3n}{2}$

The number  of comparisons needed is at least $\cfrac{3}{2}n$ if we consider the elements to be distinct.

Hence C is the answer.

Another more intuitive way to understand this is the build heap operation. I’ll leave that to you...

Comments

@Deepak Poonia Sir can you please explain all the cases of this question? It has appeared so many times and I’m facing difficulty in deriving the result every time.

---

+1

Answer 2

C.

We will use the tournament approach to get the min and max elements. (Array element is analogous to Player)

1. Considering there are n players in the tournament, the first round will have $n/2$ matches. A player is considered to be the winner if he has a higher rank than his opponent. In this stage we did 1 comparison for selecting winner or loser from 1 match, so total $n/2$ comparison for $n/2$ matches.
2. After the first round, we will keep all the losers of first round in one area and all the winners in the second area. Note how each area will have $n/2$ players in them.
3. Now from the losers pool we will find the minimum rank player by doing individual comparison. Since this pool has only $n/2$ players we can find the player with lowest rank by doing $(n/2) – 1$ comparisons. This lowest rank player corresponds to the minimum array in the element.
4. Similarly we will find the highest rank player from the pool of winners by doing $(n/2) – 1$ comparisons again. The highest rank player corresponds to the maximum element in the array.

Hence total comparisons needed to find minimum and maximum = t = $(n/2) + ((n/2)-1) + ((n/2)-1) = 3n/2 - 2$

Hence $t > n$ but $t < 3n/2$

Comments

• Nice bro!!

Answer 3

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

---

What are your current thoughts?

Answer 4

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