Wie ist die durchschnittliche und die schlechteste Fallkomplexität bei Einfügen und Indizieren in einem Python-Wörterbuch?

In Python wird das Wörterbuch auf Basis einer Hashtabelle implementiert. Die durchschnittliche Zeitkomplexität der Einfüge- und Indexierungsoperationen (Schlüssel suchen) beträgt O(1), also konstant. Im schlimmsten Fall, wenn viele Kollisionen auftreten, kann die Komplexität auf O(n) abfallen, wobei n die Anzahl der Elemente im Wörterbuch ist. Dank guter Hash-Funktion und dynamischer Erweiterung der Tabelle tritt der schlechteste Fall jedoch sehr selten auf.