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

В структуре данных типа множество (например, Set в Swift или HashSet в других языках) операция вставки элемента обычно имеет амортизированную временную сложность O(1). Это достигается за счёт использования хеш-таблиц, где элемент помещается в корзину по хешу.

Однако в худшем случае, если происходит много коллизий хешей, сложность может деградировать до O(n), где n — количество элементов в множестве. Но на практике такие случаи редки, и вставка считается эффективной.