The Gateway to Computer Science Excellence
+1 vote

in Algorithms by Loyal (5.7k points) | 78 views
yes how according to me answer still be nlogn
exaplain first how you get?
according to me at each level n comparisons total logn levels so nlogn
okk got it question is asking minimum number of comparisons that will be n/2 at each level
yes .....exactly you got it :)

i think it should be nlogn-n+1

how nitish ? i go for simple aprroch plz explain

@Anu sir,

i cant explain it completely here because it require too much working, but can give hint how i did it.

 merging two lists we need in worst case (m+n-1) comparsions...

calculating with above fact taken into account, it will give nlogn-n+1 = O(nlogn) comparisons

I think question is talking about 2-way merge sort.

At the last level, there will be n/2 comparisons.
At the second last level, there will be n/2 list each conataing 2 elements, worst case comparisons (m+n-1) = 3
there are n/4 list comparisons, each needs 3 comparisons.
total comparisons: 3*n/4

at the third last level, there are n/4 lists each having 8 elements, n/8 pairs for for comparison, worst case number of comparisons = 8+8-1 = 15

at 4th last level, each list contains 16 elements, n/8 total lists, and n/16 pairs for comparisons. worst case comparisons = 16+16-1 = 31

total comparisons =
=n/2 + 3*n/4 + 15*n/8 + 31*n/16 + ....  (in worst case)

In question, minimum number of comparisons are asked:
at last level = n/2 comparisons
at second last level = n/2 lists, n/4 pairs, each needs 2 comparisons, total comparisons = (n/4)*2 = (n/2)
Aat third last leevl = n/4 lists, n/8 pairs, best comparisons = 4, total comparisons = (n/8)*4 = n/2

such way, logn terms of (n/2) total cost = (nlogn/2).

try to take for n=4, with (nlogn / 2) it will give 4 comparisons, but actually it will take 5 comparisons.
there are two lists each of size 4,
|1|2|3|4|       |10|20|30|40|

1,2,3, and 4 will be compared with 10, when either list becomes empty i will copy all the elements of second list. only min(m,n) comparisons are required in the best case.
i am taking about worst case.

1 Answer

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+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
by Junior (511 points)

No related questions found

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,359 users