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

В Python множество (set) реализовано на основе хэш-таблицы. Операция добавления элемента в множество в среднем имеет временную сложность O(1) — то есть выполняется за константное время.

Это достигается за счёт вычисления хэш-кода элемента и вставки его в соответствующую ячейку внутренней структуры. Однако в худшем случае (при большом количестве коллизий) сложность может деградировать до O(n), где n — количество элементов в множестве.

Пример:

s = set()
s.add(42)  # Добавление элемента выполняется примерно за O(1)