Каква е времевата сложност при добавяне на нов елемент към речника?

Времевата сложност при добавяне на нов елемент към речник (например, Dictionary в Swift или NSMutableDictionary в Objective-C) обикновено е O(1) в средния случай. Това се дължи на факта, че речникът е реализиран на базата на хеш таблица, където изчисляването на хеша и вмъкването се извършват за константно време.

Въпреки това, в най-лошия случай, при колизии или необходимост от разширяване на вътрешния масив, сложността може временно да се увеличи до O(n), където n е броят на елементите.

Пример в Swift:

var dict = [String: Int]()
dict["key"] = 42 // Добавяне в средния случай за O(1)