I have the following algorithm that finds the items in common of two sorted lists:

findIntersection(List1, List2) {
    list intersection;
    int i = 0;
    int j = 0;
    while i < size of List1 and j < size of List2 {
        if List1[i] < List2[j] {
            i  ;
        }
        else if List1[i] > List2[j] {
            j  ;
        }
        else {
            add List1[i] to intersection;
            i  ;
            j  ;
        }
    }
    return intersection;
}

I think the time complexity is O(m n), but what if I know that the size of List2 is greater than the size of List1?

My conclusion was that it would still be O(m n) because in a worst case scenario where both lists have no items in common, the algorithm will still have to visit every single item in both lists, independent of their size. For example, if List1 = {10, 20, 100} and List2 = {5, 15, 25, 35, 45, 55, 65, 75, 85, 95}. But I read online that in algorithms where the time complexity is O(m n), it we know that n>m, it becomes O(n), so now I am not sure I am correct.

CodePudding user response：

It would be O(x), x being whichever of n and m is greater. Assuming n>m, in the worst-case scenario, it would be O(m (n-m)) which is still O(n).

CodePudding user response：

You're right in your thinking, the loop will never run only n times as long as m > 1. And it is always true to say that the complexity is O(n m). But think about this:

If you know that n > m, then n m < n n = 2n.

So then O(n m) = O(2n) = O(n).