Какова временная сложность операции добавления нового элемента в словарь?

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

Однако в худшем случае, при коллизиях или необходимости расширения внутреннего массива, сложность может временно возрасти до O(n), где n — количество элементов.

Пример на Swift:

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