Je vyhľadávanie prvku v slovníku v Pythone vždy operáciou s konštantnou zložitosťou?

Vyhľadávanie prvku v slovníku (dict) v Pythone má zvyčajne amortizovanú časovú zložitosť O(1), teda konštantnú. Toho sa dosahuje použitím hash tabuľky.

Avšak, v zriedkavých prípadoch, napríklad keď je veľa kolízií alebo ak hash funkcia zle rozdeľuje kľúče, môže sa zložitosť zhoršiť na O(n), kde n je počet prvkov v slovníku.

Preto vyhľadávanie nie je vždy prísne O(1), ale v praxi a vo väčšine prípadov je presne také.