Mekkora az időbeli komplexitású egy új elem hozzáadása a szótárhoz?

Egy új elem hozzáadásának időbeli komplexitása egy szótárhoz (például Swift-ben Dictionary vagy Objective-C-ben NSMutableDictionary) általában O(1) átlagosan. Ez annak köszönhető, hogy a szótár egy hash-táblán alapul, ahol a hash számítása és a beszúrás konstans időt vesz igénybe.

Azonban a legrosszabb esetben, ütközések vagy a belső tömb bővítése esetén, a komplexitás ideiglenesen O(n)-re nőhet, ahol n az elemek száma.

Swift példával:

var dict = [String: Int]()
dict["key"] = 42 // Átlagosan O(1) beszúrás