merging and sorting 2 sorted arrays with big o looking for clarification.

Question

This is a school work. I am not looking for code help but since my teacher isn't helping I came here.

I am asked to merge and sort two sorted arrays following two cases:

1. When sizes of the two arrays are equal
2. When sizes of the two arrays are different

Now I have done case 2 which also does case 1 :/ I just don't get it how I could write a code for case 1 or how it could differ from case 2. array length doesn't connect with the problem or I am not understanding correctly.

Then I am asked to compute big(o).

I am not looking for code here. If anyone by any chance understands what my teacher is asking really please give me hints to solve it.

Answer 1

It is very good to learn instead of copying.
as you suggest, there is no difference between case 1 and 2 but the worst case of algorithms depend on your solution. So I describe my solution (no code) and give you its worst case.
You can in both case, the arrays must ends with infinity so add infinity to them. then iterate over all of elements of each array, at each time, pick the one which is smaller and put in in your result array (merge of tow arrays).
With this solution, you can calculate worst case easily. we must iterate both of arrays once, and we add a infinity to both of them, if their length is n and m so our worst and best case is O(m + n) (you do m + n + 2 - 1 comparison and -1 because you don't compare the end of both array, I mean infinity)

but why adding infinity add the end of array? because for that we must make a copy of array with one more space? it is one way and worst case of that is O(m + n) for copying arrays too. but there is another solution too. you can compare until you get at the end of array, then you must add the rest of array which is not compared completely to end of your result array. but with infinity, it is automatic.

I hope helped you. if there is something wrong, comment it.

Answer 2

Merging two sorted arrays is a linear complexity operation. This means in terms of Big-O notation it is O(m+n) where m and n are lengths of two sorted arrays.

So when you say the array length doesn't connect with the problem your understanding is correct. Irrespective of the lengths of two sorted arrays the merging of these arrays involves taking elements from each sorted array and comparing them and copying the one to new array(depending whether you want the merged sorted array in ascending or descending order) and incrementing the counter of the array from which you copied the element to new sorted array.