@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?

The Gateway to Computer Science Excellence

+35 votes

Best answer

+12 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

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

+8 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

@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).

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).

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,689 answers

199,290 comments

107,279 users