Big O of sets

[Tim Peters]

[Tony Meyer]
> ...
> In particular, I'm interested in intersection, union and > (proper
> subset), and of ImmutableSets, rather than Sets.

Mutable vs immutable makes no real difference for these.

intersection uses len(little) dict lookups, where little and big are the
inputs, and little is the smaller set.  It also does a number of dict
insertions equal to the size of the result set.  Expected time is thus
O(len(little)) (the result set can't be bigger than little, so O() covers
that too).

union has the same complexity as dict.copy() followed by dict.update().

s1 < s2 is constant-time if len(s1) >= len(s2).  If the result is true, it
requires len(s1) dict lookups to determine that.  If the result is false and
len(s1) < len(s2), expected time depends on the distribution of elements.
In the worst case it requires len(s1) dict lookups to find an element of s1
not in s2.  In the best case, one dict lookup finds an element of s1 not in
s2.