Jaka jest złożoność czasowa dodawania nowego elementu do słownika?

Złożoność czasowa dodania nowego elementu do słownika (np. Dictionary w Swift lub NSMutableDictionary w Objective-C) zazwyczaj wynosi O(1) w średnim przypadku. Wynika to z faktu, że słownik jest zaimplementowany na podstawie tablicy haszującej, gdzie obliczanie hasza i wstawianie odbywa się w czasie stałym.

Jednak w najgorszym przypadku, przy kolizjach lub konieczności rozszerzenia wewnętrznej tablicy, złożoność może tymczasowo wzrosnąć do O(n), gdzie n to liczba elementów.

Przykład w Swift:

var dict = [String: Int]()
dict["key"] = 42 // Dodanie w średnim czasie O(1)