Как определить временную сложность операции чтения элементов в множествах, реализованных в Python?

В Python множества (set) реализованы на основе хеш-таблиц.

Операция чтения (проверка наличия элемента) в множестве имеет амортизированную временную сложность O(1) — то есть она выполняется за постоянное время в среднем случае.

Это означает, что проверка, есть ли элемент в множестве, очень быстрая и не зависит от размера множества.

Пример:

s = {1, 2, 3, 4}
if 3 in s:
    print("Элемент найден")

Здесь операция 3 in s выполняется за O(1) в среднем.