CODEWITHSUNDEEP
pythonloopstime-complexity
semore_1267
semore_1267

Reputation: 1447

'if not in' time complexity

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.

Upvotes: 4

Views: 9462

Answers (1)

Oliver Dain
Oliver Dain

Reputation: 9953

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.

Upvotes: 5

Related Questions