Wat is de gemiddelde en slechtste geval complexiteit van invoegen en indexeren in een Python-woordenboek?

In Python wordt de dictionary geïmplementeerd op basis van een hashtabel. De gemiddelde tijdcomplexiteit van invoeg- en indexeerbewerkingen (zoeken op sleutel) is O(1), dat wil zeggen constant. In het slechtste geval, wanneer er veel botsingen zijn, kan de complexiteit afnemen tot O(n), waarbij n het aantal elementen in de dictionary is. Dankzij goede hashing en dynamische uitbreiding van de tabel komt het slechtste geval zeer zelden voor.