Time Complexity

Question

Given two sorted arrays A and B containing distinct elements Array length given as m and n , What is the time complexity to  find the Intersection

My query is since the length of array is given and both array contain distinct elements ( their can be common elements bw A and B). So it should be O(m) if m<n else O(n) instead of O(m+n).

Comments

Since they are already sorted, it should take O(n+m) in worst case.

---

So it should be O(m) if m<n else O(n) instead of O(m+n).

It is not like the one we do in case like O(n + n²) =O(n²) because n² is asymptotically larger than n.

Here the TC depends on length of both the arrays m and n. If m is very very large than n such that n becomes insignificant infront of m then we can say that O(m+n) = O(m) but if their sizes are comparable then it is not correct to say that O(m+n)=O(m). We need to show in our time complexity that it depends on sizes of both the arrays and not only the one which is larger.

Answer 1

To get an intuitive understanding,

Consider the inputs as:
A: 1, 3, 5, 7, 9
B: 2, 4, 6, 8, 10

Now to find the intersection, you will compare the first elements of each,
On finding that they don't match, you discard the smaller one i.e '1'
Now you have the lists as:
A: 3, 5, 7, 9
B: 2, 4, 6, 8, 10

Now you compare '3' and '2' and end up discarding '2' hence having the lists as:
A: 3, 5, 7, 9
B: 4, 6, 8, 10
.
.
 and so on...

 

So here if you see, you made m+n comparisons.

But if we had lists something like this:
A: 1,2,3,4,5
B: 1,2,3,4,5,6,7.......1000

In the first 5 comparisons itself, you will empty the list A and B and won't have any other elements to compare with elements of B and hence will simply discard them because intersection wont be possible when the other set(here, list) is empty.
So the best case would be O(m) if m is less or O(n) if n is less.

 

So worst case: O(m+n)
Best case: O(m) or O(n) whichever is less.