recategorized by
47,606 views

6 Answers

Best answer
56 votes
56 votes

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 varies as per the input. In the best case, the comparisons are $\text{min}(m,n)$ and in worst case they are $m+n-1$.

edited by
17 votes
17 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
9 votes
9 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++];
}
}
8 votes
8 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).
Answer:

Related questions

21 votes
21 votes
2 answers
1
Kathleen asked Oct 8, 2014
4,952 views
Merge sort uses:Divide and conquer strategyBacktracking approachHeuristic searchGreedy approach
18 votes
18 votes
2 answers
2
Kathleen asked Oct 8, 2014
8,456 views
Consider the following sequence of numbers:$$92, 37, 52, 12, 11, 25$$ Use Bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of ...
25 votes
25 votes
3 answers
3
Kathleen asked Oct 8, 2014
10,465 views
In a virtual memory system the address space specified by the address lines of the CPU must be _____ than the physical memory size and ____ than the secondary storage siz...