retagged by
601 views
1 votes
1 votes
Atmost how many comparisons are required to find out min and max in an array of n elements where n is even ?

Answer is atmost 1.5n - 2 comparisons.

For n=6, I tried manually and the number of comparisons comes out to be 8 but according to the formula it's 1.5(6) - 2 =7 which is lesser than 8 !

Where am I going wrong ?
retagged by

1 Answer

1 votes
1 votes
let n=6

and say array as 7,8,6,4,1,3
   divided into two parts (7,8,6) and ( 4,1,3)

  further divided into (7,8) (6) and (4,1) (3)
step 1: compare 7 and 8. here min=7 and max=8. (1 comparison)

step 2: compare 6 with min and max values (2 comparisons)

            again compare (4,1) and min=1 and max=4( 1 comparison)
       
            compare those with max and min values respectively (2 comparisons) .
            lastly, compare final min and max values with 3 (2 comparisons)

total will be 1+2+1+2+2=8 comparisons
edited by

Related questions

2 votes
2 votes
2 answers
1
iarnav asked Mar 30, 2018
1,088 views
The minimum number of comparisons required to find the minimum and the maximum of 101 numbers is ________.When n is even then it's relatively easy, but how to deal with n...
1 votes
1 votes
1 answer
2
mystylecse asked Aug 15, 2017
3,449 views
The minimum number of comparisons required to find the minimum and maximum of 60 numbers is..............
2 votes
2 votes
1 answer
3