in Algorithms retagged by
325 views
1 vote
1 vote
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 ?
in Algorithms retagged by
325 views

1 comment

0
0

1 Answer

1 vote
1 vote
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

3 Comments

If you write a program involving recursion, you will not break the problem like you showed.

It will be first broken to (7,8,6) (4,1,3). (1st level)

(7,8,6) will be broken into (7,8) and (6) (2nd level)

(4,1,3) will be broken into (4,1) and (3) (3rd level).

Here in 3rd and 2nd level you would require 3+3 = 6 comparisons and finally 2 more comparisons to get final answer at the first level which is 6+2=8.
0
0
may be the time complexity is approx value. because if we are taking the elements of these kind we are getting one more than that of the 1.5n-2.

because if I take 10 elements then I getting 14 comparisons but using the formula its 13
0
0

It's not approx. In the gate question it was atmost 1.5n - 2 comparisons which means we should not get more than 1.5n - 2 comparisons for any even number n

0
0