Complexity of *in* operator in Python

103
votes

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.

3
pythontime-complexity
It depends on the type of container, since using it with a dictionary or set will be much faster than with an array. - Greg Hewgill
@BasicWolf I have used L, so it is list - Sajad Rastegar
@Rastegar L doesn't imply a list. seq is the most common choice where one wants to imply a list. L is a terrible variable name. Single letter ones are bad, and the capital implies it's a class. Even if it was something in particular, Python is dynamic, so state it explicitly in a case like this. - Gareth Latty
L means list? My libtelepathy.so is probably outdated. - Zaur Nasibov
@GarethLatty Using lst is also a good name to define a list - Roi

3 Answers

164
votes

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.

14
votes

It depends entirely on the type of the container. Hashing containers (dict, set) use the hash and are essentially O(1). Typical sequences (list, tuple) are implemented as you guess and are O(n). Trees would be average O(log n). And so on. Each of these types would have an appropriate __contains__ method with its big-O characteristics.

-1
votes

It depends on the container you're testing. It's usually what you'd expect - linear for ordered datastructures, constant for the unordered. Of course, there are both types (ordered or unordered) which might be backed by some variant of a tree.