retagged by
1,788 views
0 votes
0 votes
i cannot understand the following explanation..how solution is (3/2)n-2???

If n is a power of 2, then we can write T(n) as:
T(n) = 2T(n/2) + 2
After solving above recursion, we get
T(n) = 3/2n -2
Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And itd oes more than 3/2n -2 comparisons if n is not a power of 2.
So, here in this case put n=100 and we will get (3/2)(100) - 2 = 148 comparison .....
retagged by

1 Answer

Best answer
1 votes
1 votes
The idea is to compare pairs of values (n/2 - 1 comparisons) to get an array of high values and an array of low values. With each of those arrays we again compare pairs of values (2 * n/2 - 1 comparisons) to get the highest and lowest values respectively.

n/2 -1 + 2*n/2 - 1 = 1.5n - 2  comparisons
selected by

Related questions

2 votes
2 votes
2 answers
1
iarnav asked Mar 30, 2018
1,092 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...
2 votes
2 votes
1 answer
2
yes asked Oct 6, 2015
1,329 views
for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)
19 votes
19 votes
8 answers
3
piyushkr asked Dec 30, 2015
43,404 views
The minimum number of comparisons required to sort 5 elements is -4567
1 votes
1 votes
1 answer
4
mystylecse asked Aug 15, 2017
3,449 views
The minimum number of comparisons required to find the minimum and maximum of 60 numbers is..............