29,210 views
64 votes
64 votes

An array of $n$ numbers is given, where $n$ is an even number. The maximum as well as the minimum of these $n$ numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

  1. At least $2n-c$ comparisons, for some constant $c$ are needed.

  2. At most $1.5n-2$ comparisons are needed.

  3. At least $n\log_2 n$ comparisons are needed

  4. None of the above

9 Answers

9 votes
9 votes

Consider n=8 elements in an array {1,4,5,8,3,2,7,9}
Lets make a tournament bracket for them, where at each stage the winner is the minimum element between the two.
 

 

As you can see, number of comparisons being done = n-1 = 7

Similarly, to find the maximum element you again will need n-1 comparisons!
So total no of comparisons to find min and max=2(n-1)
Hmm...there is one optimisation to it !!

The last level in the tree is making n/2 comparisons(4 in this case) and these are being repeated while finding the minimum and maximum! So doing the last level comparisons only once, we do n/2 comparisons less
Hence 2(n-1) - n/2 = 2n-2-n/2 = 3n/2-2

Source:https://www.quora.com/How-does-the-tournament-method-for-finding-the-maximum-and-minimum-element-in-an-array-consist-of-3n-2-2-comparisons

6 votes
6 votes
Using divider and conquer approach T(n)=2T(n/2) + 2 It comes out to be O(n) but on better analysis it is 1.5n-2 comparisons
2 votes
2 votes

i don't want to congest GATE question with much answers! but this qs need litlle derivation

edited by
Answer:

Related questions

24 votes
24 votes
4 answers
1
Kathleen asked Sep 21, 2014
10,765 views
Which of the following sorting algorithms has the lowest worse-case complexity?Merge sortBubble sortQuick sortSelection sort
21 votes
21 votes
7 answers
2
pC asked Dec 21, 2015
7,772 views
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.Which of the following is not a topological ordering?$1$ $2$ $3$ $4$ $5$ $6$$1$ $3$ $2$ $4$ $5$ $6$$1$ $3$ $2$ $4$...
36 votes
36 votes
5 answers
3
64 votes
64 votes
15 answers
4
Arjun asked Jul 6, 2016
36,697 views
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...