Какая сложность вставки и индексации в словаре в Python в среднем и в худшем случае?

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