How efficient/fast is Python's 'in'? (Time Complexity wise)
It depends on the right hand operand:
The operators
in
andnot 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
andnot 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)
.