Jaká je časová složitost přidání nového prvku do slovníku?

Časová složitost přidání nového prvku do slovníku (například Dictionary ve Swift nebo NSMutableDictionary v Objective-C) je obvykle O(1) v průměru. To je způsobeno tím, že slovník je implementován na základě hashovací tabulky, kde výpočet hashe a vložení probíhá v konstantním čase.

Nicméně v nejhorším případě, při kolizích nebo nutnosti rozšíření vnitřního pole, může složitost dočasně vzrůst na O(n), kde n je počet prvků.

Příklad ve Swift:

var dict = [String: Int]()
dict["key"] = 42 // Přidání v průměru v O(1)