Complexity of *in* operator in Python
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.
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.
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.