Qual é a complexidade algorítmica de obter um valor por chave de um dicionário em Python?

A complexidade algorítmica para obter um valor por chave de um dicionário em Python no pior caso é O(1).

Isto é possível graças ao uso de tabelas de dispersão. A chave é dispersada, e o hash obtido é usado para determinar o índice (balde) na tabela onde o valor correspondente é armazenado. No caso ideal (sem colisões de hash), o acesso a esse balde leva tempo constante.

No pior caso, com muitas colisões de hash, a complexidade pode atingir O(n), onde n é o número de elementos no dicionário. Isto acontece quando todas as chaves são dispersadas no mesmo balde, e para encontrar o valor necessário, é preciso percorrer sequencialmente todos os elementos nesse balde. No entanto, a implementação padrão de dicionários em Python usa mecanismos de resolução de colisões e rehashing para minimizar a probabilidade de tal cenário.

# Obtemos o valor pela chave
value = my_dict[key]