CODEWITHSUNDEEP
pythontime-complexity
Immanuel Weihnachten
Immanuel Weihnachten

Reputation: 284

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

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.

Upvotes: 18

Views: 12328

Answers (1)

Gareth Rees
Gareth Rees

Reputation: 65854

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.

Upvotes: 32

Related Questions