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.

Answer 1

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:).