Dark Mode

325 views

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 ?

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 ?

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

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

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.

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