4

Could someone explain the time complexity of the following loop?

for x in iterable:
    if x not in other_iterable:
        return False

I found a really good Python operation time complexity text lecture here, and saw that the time for the outer for loop was O(N). However, how does the if x not in other_iterable part factor into the time complexity? I imagine the loop will be checking x against every element in iterable until it is found, or the list is exhausted. So what would be the recommended way to make the if x not in other_iterable loop take the smallest amount of time possible? Possibly having sorted the other_iterable? I'm practically a rookie at understanding time complexity, and would like to know more.

Edit: other_iterable would be a list with possible duplicates.

semore_1267
  • 1,327
  • 2
  • 14
  • 29
  • 4
    It depends. What is the data type of `other_iterable`? If it's a list, it's O(N), but if it's a set, it's O(1). (So the whole loop is O(N^2) (well, O(NM)) or O(N), depending) – Aleksi Torhamo Mar 07 '17 at 05:09
  • 1
    @JoranBeasley No it's not, set intersection is still O(N). (Where N is the smaller of the two) – Aleksi Torhamo Mar 07 '17 at 05:12
  • Possible duplicate of [Complexity of \*in\* operator in python](http://stackoverflow.com/questions/13884177/complexity-of-in-operator-in-python) – Marat Mar 07 '17 at 05:17
  • 2
    A nice ref on collections https://wiki.python.org/moin/TimeComplexity – Selecsosi Mar 07 '17 at 05:20

1 Answers1

5

In the question you've called them iterable so I'm going to assume they're not set or similar and that to determine if x not inother_iterable is true you have to check the values in other_iterable one at a time. For example, this would be the case if they were lists or generators.

Time complexity is about the worst case; it's an upper bound. So, in this case the worst case would be in everything in iterable was in other_iterable but was the last item returned. Then, for each of the n items in iterable you'd check each of the m items in other_iterable and the total number of operations would be O(n*m). If n is roughly the same size then it's O(n^2).

For example, if iterable = [8, 8, 8] and other_iterable = [1, 2, 3, 4, 5, 6, 7, 8] then for each of the 3 items in iterable you have to check the 8 items in other_iterable until you find out that your if statement is false so you'd have 8 * 3 total operations.

The best case scenario would be if the first item in iterable was not in other_iterable. Then you'd only examine a single element of iterable but you'd iterate over all m items in other_iterable until you learned that the if condition was true and you'd be done. That's a total of m operations. However, as noted above, big-O time complexity is about worst case scenarios so you wouldn't ordinarily quote this as the complexity.

Oliver Dain
  • 9,617
  • 3
  • 35
  • 48