Python isDisjoint() runtime

Question

What is the algorithmic runtime of Python 2.7's isDisjoint(other) method for sets? Is it faster than simply doing intersection(other) and then checking len()>0 of that returned intersection?

Answer 1

The complexity in both cases is going to be O(min(len(s), len(t)). The only difference is that intersection creates a new set of all matched items and isdisjoint simply returns a boolean and can short-circuit as soon as a match is found.

Example that short-circuits right away:

>>> s1 = set(range(10**6))
>>> s2 = set([0] + list(range((10**6), 2 * (10**6))))
>>> s1.intersection(s2)
set([0])
>>> %timeit s1.isdisjoint(s2)
10000000 loops, best of 3: 94.5 ns per loop
>>> %timeit s1.intersection(s2)
100 loops, best of 3: 6.82 ms per loop

In this case the timings are close to each other, suggesting the matched item was found pretty late during the loop.

>>> s1 = set(range(10**6))
>>> s2 = set(range((10**6) - 1, 2 * (10**6)))
>>> s1.intersection(s2)
set([999999])
>>> %timeit s1.isdisjoint(s2)
100 loops, best of 3: 5.37 ms per loop
>>> %timeit s1.intersection(s2)
100 loops, best of 3: 6.62 ms per loop