According to https://wiki.python.org/moin/TimeComplexity, x in s operation take O(n) in worst case.
Since set use hash internally, I think it should be O(1) instead of O(n)?
Asked
Active
Viewed 28 times
0
user3595632
- 4,692
- 8
- 43
- 95
-
The worst case is that the hash of every single item in the set collides. – jonrsharpe May 06 '17 at 09:38
-
@jonrsharpe, Thanks. One question. If every single item had same hash value, how can `set()` find the item internally??... – user3595632 May 06 '17 at 09:42
-
It has to check every item for equality, i.e. falls back to `any(item == x for item in s)`. – jonrsharpe May 06 '17 at 09:43