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

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

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

На практике благодаря хорошей реализации и динамическому расширению словаря вставка работает очень быстро и эффективно.