Qual é a complexidade temporal de adicionar e remover um elemento em um dicionário em Python?

Em Python, o dicionário é implementado com base numa tabela de hash, o que garante uma complexidade temporal O(1) em média para operações de adição e remoção de elementos.

• Adicionar elemento: calcula-se o hash da chave, e o elemento é inserido na célula correspondente. Em média, isto leva um tempo constante.
• Remover elemento: também ocorre pelo hash da chave e, em média, leva O(1).

No entanto, no pior caso (por exemplo, com muitas colisões), as operações podem degradar para O(n), onde n é o número de elementos no dicionário, mas esses casos são extremamente raros graças a uma boa implementação e expansão dinâmica do dicionário.

Exemplo:

my_dict = {}
my_dict['key'] = 'value'  # adição — O(1)
del my_dict['key']          # remoção — O(1)