Kokia yra naujo elemento pridėjimo į žodyną laiko sudėtingumas?

Žodyno (pavyzdžiui, Swift Dictionary arba Objective-C NSMutableDictionary) naujo elemento pridėjimo laiko sudėtingumas paprastai yra O(1) vidutiniškai. Tai yra todėl, kad žodynas įgyvendintas naudojant maišos lentelę, kur skaičiavimas ir įterpimas vyksta pastoviu laiku.

Tačiau blogiausiu atveju, susidūrus su kolizijomis arba reikalingumu išplėsti vidinį masyvą, sudėtingumas laikinai gali išaugti iki O(n), kur n yra elementų skaičius.

Pavyzdys Swift:

var dict = [String: Int]()
dict["key"] = 42 // Vidutiniškai įterpimas O(1)