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

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

Оценка предполагает нормальное распределение хешей и ограниченную стоимость вычисления hash и сравнения ключей. Для пользовательских объектов эти операции сами могут быть дорогими. При серии вставок стоимость периодических расширений распределяется по многим операциям. Если ключ уже существует, обновляется значение; число элементов при этом не увеличивается.