Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Time complexity of python set operations?

What is the the time complexity of each of python's set operations in Big O notation?

I am using Python's set type for an operation on a large number of items. I want to know how each operation's performance will be affected by the size of the set. For example, add, and the test for membership:

myset = set() myset.add('foo') 'foo' in myset 

Googling around hasn't turned up any resources, but it seems reasonable that the time complexity for Python's set implementation would have been carefully considered.

If it exists, a link to something like this would be great. If nothing like this is out there, then perhaps we can work it out?

Extra marks for finding the time complexity of all set operations.

like image 691
Stephen Emslie Avatar asked Sep 08 '11 16:09

Stephen Emslie


People also ask

What is time complexity of set in Python?

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 table's load factor is too high, then you face collisions and O(n).

Are set operations fast in Python?

set is as fast as it gets. However, if you rewrite your code to create the set once, and not change it, you can use the frozenset built-in type. It's exactly the same except immutable. If you're still having speed problems, you need to speed your program up in other ways, such as by using PyPy instead of cPython.

What is the time complexity of in operation in Python?

The average time complexity of the in operator for sets is O(1) . It does not depend on the number of elements. The execution time does not change depending on the value to look for. If you want to repeat in operation for a list with many elements, it is faster to convert it to a set in advance.

What is the complexity of set intersection Python?

What's the time complexity of set intersection in Python? The time complexity of set intersection in Python on a set with n elements and a set argument with m elements is O(min(n, m)) because you need to check for the smaller set whether each of its elements is a member of the larger set.


1 Answers

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 table's 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.

like image 118
Sergey Romanovsky Avatar answered Oct 12 '22 20:10

Sergey Romanovsky