If we have two sorted array of size 'a' and 'b' and "one array smallest element is greater than largest element of other one".Then in the merge procedure, what will be its time complexity?

Question

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

Answer 1

then the complexity will be O(a+b) because merge procedure isnt in place . And the comparisons required is min of a,b .

Comments

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)

Answer 2

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

Comments

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