Временная сложность проверки равенства двух замороженных наборов в Python

Поскольку справочные документы ничего не говорят об этом, это зависит от реализации, поэтому нет ответа, кроме просмотра исходного кода используемой вами версии Python (в вашем дистрибутиве CPython Objects/setobject.c). Глядя на источник для Python 3.7.0, ответ "может быть" ;-)

Равенство сначала проверяет, имеют ли замороженные наборы одинаковый размер (len()). Если нет, то они не могут быть равны, поэтому сразу возвращается False.

В противном случае хеш-коды сравниваются, если они уже были вычислены. Если они уже были вычислены, то сразу возвращается False, если хэш-коды не равны. В противном случае вызывается поэлементный код, чтобы проверить, является ли один подмножеством другого.

Хэш-код для замороженного набора вычисляется не просто так — это были бы расходы, которые могут не окупиться. Так что что-то должно заставить его. Основной вариант использования замороженных наборов в начале состоял в том, чтобы разрешить наборы наборов, а в этом хеш-коде контекста будут вычисляться как обычная часть добавления замороженного набора в содержащий набор. Реализация набора C-уровня содержит слот для записи хэша, если и когда он вычисляется, который инициализируется значением -1 (зарезервированное значение, означающее "внутренне неизвестен хэш-код").

hash(x) == hash(y) не означает, что x == y:

>>> help(hash)
hash(...)
    hash(object) -> integer

    Return a hash value for the object.  Two objects with the same value have
    the same hash value.  The reverse is not necessarily true, but likely.

поэтому, чтобы сравнить два значения frozenset на равенство, вам все равно нужно проверить, что оба набора имеют одинаковый размер, а затем проверить, есть ли каждый элемент в одном также и в другом.

Я оставляю в качестве упражнения для читателя, у которого много свободного времени, чтобы найти два разных frozenset с одинаковым значением хеш-функции.