Wat is de tijdcomplexiteit van het toevoegen van een nieuw element aan het woordenboek?

De tijdscomplexiteit van het toevoegen van een nieuw element aan een woordenboek (bijvoorbeeld Dictionary in Swift of NSMutableDictionary in Objective-C) is meestal O(1) in het gemiddelde geval. Dit komt doordat het woordenboek is geïmplementeerd op basis van een hash-tabel, waar de hash-berekening en het invoegen in constante tijd plaatsvinden.

In het slechtste geval, bij collisions of de noodzaak om de interne array uit te breiden, kan de complexiteit tijdelijk toenemen tot O(n), waarbij n het aantal elementen is.

Voorbeeld in Swift:

var dict = [String: Int]()
dict["key"] = 42 // Toevoegen in O(1) gemiddeld