# data structures – Time complexity of python set operations?

## data structures – Time complexity of python set operations?

According to Python wiki: Time complexity, **set** is implemented as a hash table. So you can expect to lookup/insert/delete in **O(1)** average. Unless your hash tables load factor is too high, then you face collisions and O(n).

P.S. for some reason they claim O(n) for delete operation which looks like a mistype.

P.P.S. This is true for CPython, pypy is a different story.

The operation `in`

should be independent from he size of the container, ie. *O(1)* — given an optimal hash function. This should be *nearly* true for Python strings. Hashing strings is always critical, Python should be clever there and thus you can expect near-optimal results.

#### data structures – Time complexity of python set operations?

The other answers do not talk about 2 crucial operations on sets: Unions and intersections. In the worst case, union will take O(n+m) whereas intersection will take O(min(x,y)) provided that there are not many element in the sets with the same hash. A list of time complexities of common operations can be found here: https://wiki.python.org/moin/TimeComplexity