The complextiy of Python issubset()

Question

Given two sets A and B and their length: a=len(A) and b=len(B) where a>=b. What is the complextiy of Python 2.7's issubset() function, ie, B.issubset(A)? There are two conflicting answers I can find from the Internet:

1, O(a) or O(b)

found from:https://wiki.python.org/moin/TimeComplexity and bit.ly/1AWB1QU

(Sorry that I can not post more http links so I have to use shorten url instead.)

I downloaded the source code from Python offical website and found that:

def issubset(self, other): """Report whether another set contains this set.""" self._binary_sanity_check(other) if len(self) > len(other): # Fast check for obvious cases return False for elt in ifilterfalse(other._data.__contains__, self): return False return True

there is only loop here.

2, O(a*b)

found from: bit.ly/1Ac7geK

I also found some codes look like source codes of Python from: bit.ly/1CO9HXa as following:

def issubset(self, other): for e in self.dict.keys(): if e not in other: return False return True

there are two loop here.

So which one is right? Could someone give me a detailed answer about the difference between the above two explanations? Great thanks in advance.

NPE · Accepted Answer · 2014-12-28 07:06:15Z

The complexity of B.issubset(A) is O(len(B)), assuming that e in A is constant-time.

This a reasonable assumption generally, but can be easily violated with a bad hash function. If, for example, all elements of A had the same hash code, the time complexity of B.issubset(A) would deteriorate to O(len(B) * len(A)).

In your second code snippet, the complexity is the same as above. If you look closely, there is only one loop; the other is an if statement (if e not in other:).

Collectives™ on Stack Overflow

The complextiy of Python issubset()

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related