2 votes

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 \text{ and } t\leq 2n-2$
- $t>n \text{ and } t\leq 3\lceil \frac{n}{2}\rceil$
- $t>\lceil \log_2(n)\rceil \text{ and } t\leq n$

5 votes

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

2 votes

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

1 vote

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

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

0 votes

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.