Wat is de tijdcomplexiteit van de operatie om een element aan een woordenboek toe te voegen?

In woordenboeken (bijvoorbeeld Dictionary in Swift) heeft de operatie om een element toe te voegen meestal een geamortiseerde tijdscomplexiteit van O(1). Dit wordt bereikt door gebruik te maken van hashtabellen, waarbij de hash-berekening van de sleutel en de invoeging gemiddeld in constante tijd plaatsvinden. In het slechtste geval, bijvoorbeeld 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 in het woordenboek is.