How efficient/fast is Python's 'in'? (Time Complexity wise)

Question

In Python, what is the efficiency of the in keyword, such as in:

a = [1, 2, 3] if 4 in a:   ... 

Answer 1

The complexity for lists is:

O(n) 

For sets it is:

O(1) 

http://wiki.python.org/moin/TimeComplexity

Answer 2

It depends on the right hand operand:

The operators in and not in test for collection membership. [...] The collection membership test has traditionally been bound to sequences; an object is a member of a collection if the collection is a sequence and contains an element equal to that object. However, it make sense for many other object types to support membership tests without being a sequence. In particular, dictionaries (for keys) and sets support membership testing.

Classes can implement the special method __contains__ to override the default behavior (iterating over the sequence) and thus can provide a more (or less) efficient way to test membership than comparing every element of the container.

The membership test operators (in and not in) are normally implemented as an iteration through a sequence. However, container objects can supply the following special method with a more efficient implementation, which also does not require the object be a sequence.

---

Since you have a list in your example, it is iterated over and each element is compared until a match is found or the list is exhausted. The time complexity is usually O(n).