Time-complexity of checking if two set are equal in Python

Question

Reading this question, I wondered how much time (asymptotically speaking) does it takes to Python to evaluate expressions like

{1,2}=={2,1}

that is to say, to check if two instances of the set class are equal.

Answer 1

Comparison between sets is implemented by the function set_richcompare in setobject.c, line 1848. You'll see that equality is implemented as follows:

1. If the sets do not have the same size, return false.

2. If both sets have been hashed, and the hashes differ, return false.

3. Call set_issubset.

The subset test for two sets looks like this:

while (set_next(so, &pos, &entry)) {
    int rv = set_contains_entry((PySetObject *)other, entry);
    if (rv == -1)
        return NULL;
    if (!rv)
        Py_RETURN_FALSE;
}
Py_RETURN_TRUE;

You'll see that it works by iterating over all the elements of the first set and then looking up each one in the other set. So (unless there are a lot of hash collisions) this is linear in the size of the first set.