Time complexity for merging two sorted arrays of size n and m

[The Encapsulator]

I was just wondering what is the time complexty of merging two sorted arrays of size n and m, given that n is always greater than m.

I was thinking of using merge sort, which I assume in this case will consume O(log n+m).

I am not really good with big-oh and stuff. Please suggest me the time complexity for this problem and let me know if there is an even optimized way of solving the problem.

Thanks in advance.

[doug4]

Big-O is the complexity of the worst case scenario.

If the two lists are already sorted, the complexity would be O(n + m). It matters not the relative sizes of n and m. Consider this worst case: The last element of n is larger than the 2nd last element of m (edit: or there is only 1 element of m), but smaller than the last element of m.

The algorithm is simple: compare the first element of m and the first element of n. Remove the smaller from its initial list and put it in the merged list. Now compare the new first elements. Keep doing this until one list is empty. Then put the remaining elements of the other list in the merged list.

Because in the worst case all elements except the last are compared against another element and moved into merged list, there are (m + n - 1) comparisons. Constants are ignored because they become trivial as m and n become very large. So the complexity of this algorithm is O(m + n).

[doug4]

Mergesort would be O( (n + m) log(n+m) ), because it must do the sorting. Since your 2 arrays are already sorted individually, you can skip the sorting and just do the merge.