Intersection complexity

Question

In Python you can get the intersection of two sets doing:

>>> s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> s2 = {0, 3, 5, 6, 10}
>>> s1 & s2
set([3, 5, 6])
>>> s1.intersection(s2)
set([3, 5, 6])

Anybody knows the complexity of this intersection (&) algorithm?

EDIT: In addition, does anyone know what is the data structure behind a Python set?

Answer 1

The intersection algorithm always runs at O(min(len(s1), len(s2))).

In pure Python, it looks like this:

    def intersection(self, other):
        if len(self) <= len(other):
            little, big = self, other
        else:
            little, big = other, self
        result = set()
        for elem in little:
            if elem in big:
                result.add(elem)
        return result

[Answer to the question in the additional edit] The data structure behind sets is a hash table.