Cum se evaluează complexitatea temporală a căutării unui element după cheie într-un depozit de date sub formă de dicționar?

În Python, dicționarul este implementat pe baza unei tabele hash, așa că căutarea unui element după cheie se face în medie în O(1) — timp constant. Acest lucru se realizează datorită calculului funcției hash a cheii și accesului rapid la celula corespunzătoare.

Cu toate acestea, în cel mai rău caz, de exemplu, în cazul multor coliziuni, complexitatea temporară poate să se degradeze la O(n), unde n este numărul elementelor din dicționar. În practică, astfel de cazuri sunt rare datorită unei implementări bune a funcțiilor hash și extinderii dinamice a dicționarului.