Time complexity O(m+n)

I’m not sure why the time complexity for this solution is O(m+n).

Isn’t this “searching” for an element from list2 against list1, so number of elements in list2 n * O(1) = O(n)?

If it’s regarding the worst-case scenario, then isn’t it O(m x n)?

Type your question above this line.


The time complexity also includes the time you take to build the hash table, which is O(m). So total time complexity is:
time taken to build hash table of m elements + time taken to lookup n elements = O(m + n)

You will see similar examples again for graph algorithms (maybe not this course).