Qual é a complexidade temporal de adicionar um novo elemento ao dicionário?

A complexidade temporal de adicionar um novo elemento a um dicionário (por exemplo, Dictionary em Swift ou NSMutableDictionary em Objective-C) geralmente é O(1) na média. Isto deve-se ao facto de o dicionário ser implementado com base numa tabela de dispersão, onde o cálculo do hash e a inserção ocorrem em tempo constante.

No entanto, no pior caso, em caso de colisões ou necessidade de expandir o array interno, a complexidade pode temporariamente aumentar até O(n), onde n é o número de elementos.

Exemplo em Swift:

var dict = [String: Int]()
dict["key"] = 42 // Inserção em O(1) na média