retagged by
16,454 views
33 votes
33 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?

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

4 Answers

Best answer
20 votes
20 votes

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

edited by
14 votes
14 votes

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$

8 votes
8 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|

2 votes
2 votes
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:

Related questions

18 votes
18 votes
3 answers
1
Arjun asked Feb 18, 2021
11,513 views
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$?$\Theta(...
10 votes
10 votes
3 answers
2
Arjun asked Feb 18, 2021
8,224 views
Consider the following sequence of operations on an empty stack.$$\textsf{push}(54);\textsf{push}(52);\textsf{pop}();\textsf{push}(55);\textsf{push}(62);\textsf{s}=\texts...
11 votes
11 votes
1 answer
4