The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
4k views

For merging two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, we require comparisons of

  1. $O(m)$

  2. $O(n)$

  3. $O(m+n)$

  4. $O(\log m + \log n)$

asked in Algorithms by Veteran (59.7k points)
edited by | 4k views

4 Answers

+28 votes
Best answer

Answer: Option C.

The number of moves are however always $m+n$ so that we can term it as $\Theta(m+n)$. But the number of comparisons vary as per the input. In the best case the comparisons are $Min(m,n)$ and in worst case they are $m+n-1$.

answered by Boss (19.9k points)
edited by
0
@Arjun Sir I think its not rght to say best case as Min(m,n). It depnds like if m>n and whichever side will contain smaller values will be finished first. It may be m or n not always minimum.. ryt sir?
+1
not always- thats why it is only a best case.
+1
ohh.. ok sir. Thnx :)
+11 votes
A : 10  20  30  90

B. : 40  50  60  70

Suppose A.length =m ,B.length=n


Here m+n-1 comparisons are required
So O(m+n)//this is one of  the worst case comparison
answered by Boss (23k points)
0
Thanks for the example
+7 votes

If there are 2 arrays like this

A: 10   20    60   90

B:  30   50    70  100

And store the resultent array in C[ ]

while((a[]!=NULL) && (b[]!=NULL))
{
if((a[i]<b[j])||(b[j]==NULL))
{
    c[k++]=a[i++];
}
else
{
    c[k++]=b[j++];
}
}
answered by Veteran (103k points)
+6 votes
@srestha, kindly notice that in question its written two sorted list, not array.

in this case,
best case:- all elements of 2nd list is greater than that of 1st list then minimum comparison is Min(m,n) as it will take only one iteration.for comparison rest will be inserted as it is.
and worst case:- let 2 sorted list be 1,2,3,4 and 1,2,3,4 so here total comparison for merging should be =7(last element need not be compared) so total comparison= m+n-1= O(m+n).
answered by (149 points)
0
How are you knowing that you have reached the last element of one of the sorted lists? Doesn't that require another comparison?

Related questions



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

44,019 questions
49,545 answers
162,708 comments
65,769 users