educative.io

Educative

How is the time complexity O(m+n)?

Referring to this question: Educative: Interactive Courses for Software Developers
For each element in a sublist of size m if we go through each of the elements of the super list of size n, how is the time complexity shown to be O(m + n)? It is O(m X n), isn’t it?

Hello @Sonal_Pandey,

Finding the presence of an element in the sub-list of size m follows O(1) time complexity. This is because the sub-list is a set in this case and acts as a hash table under the hood. So essentially, we are iterating in a linear fashion over the super-list of size n and checking the presence of elements in the sub-list of size n. Hence, the time complexity will be O(m +n). Main point to note here is that we are not iterating over the sub-list.

Hope this helps!