Each Answer to this Q is separated by one/two green lines.
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.
The complexity of
in depends entirely on what
e in L will become
See this time complexity document for the complexity of several built-in types.
Here is the summary for
- 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 (
set) use the hash and are essentially O(1). Typical sequences (
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.