retagged by
661 views
1 votes
1 votes

retagged by

1 Answer

0 votes
0 votes
I think the formula for the no of comparison should be n/2 + 3*n/4 + 7*n/8 + 15*n/16 + ....  

=(2-1)n/2 + (4-1)*n/4 + (8-1)*n/8 + 1(6-1)*n/16.....

=(n-n/2)+(n-n/4)+(n-n/8)+......log n times

=nlogn-(n+n/2+n/4.........)

=nlogn-n+1 is the answer  for no of comparisons in worst case  but in the given question it is asking about the minimum  no of comparisons i.e. in best case for every level it will perform n/2 comparisons logn times.So the answer is  nlogn/2.

We have to  keep in mind that no of comparisons is not equal to asymptotic time complexity

Related questions

3 votes
3 votes
2 answers
1
2 votes
2 votes
1 answer
2
0 votes
0 votes
1 answer
3
raja11sep asked Jan 15, 2022
831 views
Can anyone explain each option, for every option if it is true then why? If false then why? (Please don’t comment like answer is A,B etc) Please help
0 votes
0 votes
1 answer
4