The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

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

asked in Programming by (175 points) | 498 views

2 Answers

+2 votes
then the complexity will be O(a+b) because merge procedure isnt in place . And the comparisons required is min of a,b .
answered by Veteran (10.3k points)
edited by
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.
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?
Yes. Exactly.
Sir what about that min(a,b)?
After min(a,b) comparisons, one array will be finished and then there won't be any more comparisons.

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?
sorry, n means a+b.
I GOT IT SIR ! thanx i was confused with it

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


O(a+b) is the right answer

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)
0 votes
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 array would become empty so we can copy elements of another array..
answered by Veteran (34.3k points)
yes. But time complexity would include copying too.
yes time complexity will be O(n) only
will the no of comparisions remain min(a,b) even when we use setinel node(infinity)??
@pooja palod O(n) means (comparison+shifting both array into new array) max(a,b)+O(a)+O(b) right??

34,291 questions
41,038 answers
39,940 users