educative.io

Time complexity O(m+n)

Courses
,
#1

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.

Course: https://www.educative.io/collection/5642554087309312/5634727314718720
Lesson: https://www.educative.io/collection/page/5642554087309312/5634727314718720/5644534738321408

#2

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).