CODEWITHSUNDEEP
python
M.M
M.M

Reputation: 1373

Time complexity of python "set.intersection" for n sets

I want to know the complexity of the set.intersection of python. I looked in the documentations and the online wikis for python, but I did not find the time complexity of this method for multiple sets.

Upvotes: 16

Views: 20547

Answers (1)

rocky
rocky

Reputation: 7098

The python wiki on time complexity lists a single intersection as O(min(len(s), len(t)) where s and t are sets with the sizes len(s) and len(t), respectively. (In English: the time is bounded by and linear in the size of the smaller set.)

Note: based on the comments below, this wiki entry had been be wrong if the argument passed is not a set. I've corrected the wiki entry.

If you have n sets (sets, not iterables), you'll do n-1 intersections and the time can be (n-1)O(len(s)) where s is the set with the smallest size.

Note that as you do an intersection the result may get smaller, so although O is the worst case, in practice, the time will be better than this.

However, looking at the specific code this idea of taking the min() only applies to a single pair of sets and doesn't extend to multiple sets. So in this case, we have to be pessimistic and take s as the set with the largest size.

Upvotes: 15

Related Questions