A busca de um elemento num dicionário em Python é sempre uma operação de complexidade constante?

A busca de um elemento num dicionário (dict) em Python geralmente tem uma complexidade de tempo amortizada de O(1), ou seja, constante. Isso é alcançado através do uso de uma tabela de dispersão.

No entanto, em casos raros, por exemplo, quando há muitas colisões ou se a função de hash distribui mal as chaves, a complexidade pode piorar para O(n), onde n é o número de elementos no dicionário.

Assim, a busca nem sempre é estritamente O(1), mas na prática e na maioria dos casos, é exatamente assim.