Qual è la complessità temporale dell'aggiunta di un nuovo elemento al dizionario?

La complessità temporale di aggiunta di un nuovo elemento a un dizionario (ad esempio, Dictionary in Swift o NSMutableDictionary in Objective-C) è generalmente O(1) in media. Ciò è dovuto al fatto che il dizionario è implementato tramite una tabella hash, dove il calcolo dell'hash e l'inserimento avvengono in tempo costante.

Tuttavia, nel caso peggiore, in presenza di collisioni o necessità di espandere l'array interno, la complessità può temporaneamente aumentare fino a O(n), dove n è il numero di elementi.

Esempio in Swift:

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