Wat is de tijdcomplexiteit van het toevoegen en verwijderen van een element in een Python-woordenboek?

In Python wordt een woordenboek geïmplementeerd op basis van een hash-tabel, wat gemiddeld een tijdcomplexiteit van O(1) biedt voor het toevoegen en verwijderen van elementen.

• Element toevoegen: de hash van de sleutel wordt berekend en het element wordt in de bijbehorende cel geplaatst. Gemiddeld kost dit een constante tijd.
• Element verwijderen: gebeurt ook via de hash van de sleutel en kost gemiddeld O(1).

In het ergste geval (bijvoorbeeld bij veel collisions) kunnen de operaties degraderen tot O(n), waarbij n het aantal elementen in het woordenboek is, maar dergelijke gevallen zijn uiterst zeldzaam dankzij een goede implementatie en dynamische uitbreiding van het woordenboek.

Voorbeeld:

my_dict = {}
my_dict['key'] = 'value'  # toevoegen — O(1)
del my_dict['key']          # verwijderen — O(1)