Qual é a complexidade média e no pior caso de inserção e indexação em um dicionário em Python?

Em Python, o dicionário é implementado com base numa tabela de hash. A complexidade temporal média das operações de inserção e indexação (procura por chave) é O(1), ou seja, constante. No pior caso, quando ocorrem muitas colisões, a complexidade pode degradar-se para O(n), onde n é o número de elementos no dicionário. No entanto, graças a uma boa função de hash e à expansão dinâmica da tabela, o pior caso ocorre muito raramente.