Search code examples
pythonsetcomplexity-theory

Intersection complexity

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?

Solution

  • The answer appears to be a search engine query away. You can also use this direct link to the Time Complexity page at python.org. Quick summary:

    Average:     O(min(len(s), len(t))
Worst case:  O(len(s) * len(t))

    EDIT: As Raymond points out below, the "worst case" scenario isn't likely to occur. I included it originally to be thorough, and I'm leaving it to provide context for the discussion below, but I think Raymond's right.