is this the best algorithm for this problem??

Question

I solved the problem described in the following link. I summed it up in my code.
I was wondering about the running time of the algorithm I wrote. Please correct me if I am wrong:

Let n, m be the size of the arrays, then:

1. Both arrays need to be sorted, which takes O(nlogn) and O(mlogm)
2. You need to go in the worst case scenario through at least n rows and m columns, which sums up to be O(n + m)

Now, then the complexity turns out to be: O(nlogn) + O(mlogm) + O(n + m) which is just O(nlogn) where n > m

is that correct?

The second thing I wanted to ask is what would be the value No for which this algorithm takes over the brute force approach whose complexity is O(n^2)?

Is there any other better algorithm for this problem?
https://code.sololearn.com/caWtzLo474eI/?ref=app

Answer 1

Your maths is correct.

To find out when your O(n log n) overtakes the simple O(n²) you just have to run tests, a lot of the constant factors can be hidden in the `sort` function and we have no real way of telling.