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!