498 views

P.S. Applied conditions given in " " is applicable on any(as per choice)

then the complexity will be O(a+b) because merge procedure isnt in place . And the comparisons required is min of a,b .
edited
+1
If input is always given like that then you are right- but that is not the question- it is telling only for a particular input- merge algorithm is designed without this knowledge. And you are right in 1 comparison to identify the property- but then we have to modify the standard merge procedure to do this.
+1
Ok i got it sir..that means there will be no such benefit if this condition holds for one such input....the merge procedure still remains O(n)...isnt it sir?
+1
Yes. Exactly.
0
0
After min(a,b) comparisons, one array will be finished and then there won't be any more comparisons.
0
sir,

i can't understand that how O(n) as there is no mention about total size of both array as n rather than a+b . I got other explanations.can you please help me out?
0
sorry, n means a+b.
+1
I GOT IT SIR ! thanx i was confused with it
0

@Arjun Sir, Suppose array A has "a" elements and array B has "b" element and a>b

And if b[0] >a[0] then in this case no. of comparison would be 'a' times.

I think in the best case no. of comparison = min(a,b)
And in the worst case no. of  comparison  = max(a,b)

Please tell me sir where I am wrong.

0

as number of comparison required is min(a,b)

but we need to take the time of copying the remaining elements of larger list into the final list thats why time complexity is O(a+b)
if one array smallest element is greater than largest element of other one comparisons will be min(a,b)...this would be best case for merge procedure..one array would become empty so we can copy elements of another array..
0
yes. But time complexity would include copying too.
0
yes time complexity will be O(n) only
0
will the no of comparisions remain min(a,b) even when we use setinel node(infinity)??
0
@pooja palod O(n) means (comparison+shifting both array into new array) max(a,b)+O(a)+O(b) right??