Search code examples
pythontime-complexitycontains

Complexity of *in* operator in Python

What is the complexity of the in operator in Python? Is it theta(n)?

Is it the same as the following?

def find(L, x):
   for e in L:
       if e == x:
           return True
   return False

L is a list.

Solution

  • The complexity of in depends entirely on what L is. e in L will become L.__contains__(e).

    See this time complexity document for the complexity of several built-in types.

    Here is the summary for in:

    • list - Average: O(n)
    • set/dict - Average: O(1), Worst: O(n)

    The O(n) worst case for sets and dicts is very uncommon, but it can happen if __hash__ is implemented poorly. This only happens if everything in your set has the same hash value.