O(n log m) vs O(n+m) - which is better?

Question

Hi Which of this time complexity is better.

O(n log m) vs O(n + m)

Analyzing these 2 algorithms, which one is better to use practicall on a large scale?

e.g) if n and m are exponentially large it becomes

O(2e) vs O(e*(something linear to e))

Sample Problem: Common elements in 2 arrays:

1) 2 pointer approach

2) Using Binary search

Answer 1

I think what you're asking is how best to find the common elements in two sorted arrays. You have the choice of two algorithms:

1. The "two-pointer" approach, which is O(m + n).
2. Using binary search to determine if the items in array N are in array M. This is O(n log m).

If the arrays are close to the same size, then the first algorithm, which is strictly linear, is preferable.

If one of the arrays is much larger than the other, then you might want to consider the binary search approach. You'll want to search the larger array for items that are in the smaller array. For example, if you have the arrays M and N, where M has 1,000,000 items and N has 100 items, you have a choice:

• Look for M in N (i.e. do 1,000,000 searches on an array of 100)
• Look for N in M (i.e. do 100 searches on an array of 1,000,000)

If you look for M in N, then the complexity is O(m log n). Here, m=1000000, and log(n)=7 (approximately)

If you look for N in M, then the complexity is O(n log m). n=100 and log(m)=20 (approximately).

It's pretty clear in that case which you want to do.

In practice, the cutoff between whether you should use the O(m+n) or O(n log m) (where n is smaller than m) algorithm can only be determined empirically. It's not just a matter of figuring whether (m + n) < (n log m), because binary search involves a bit of overhead that the two-pointer method doesn't. It's quite likely that the two pointer method would be faster even if (m + n) was double or triple (n log m).