Care este complexitatea temporală a adăugării unui element nou în dicționar?

Complexitatea temporară de adăugare a unui element nou într-un dicționar (de exemplu, Dictionary în Swift sau NSMutableDictionary în Objective-C) este de obicei O(1) în medie. Acest lucru se datorează faptului că dicționarul este implementat pe baza unui tabel de dispersie, unde calculul hash-ului și inserarea se realizează în timp constant.

Cu toate acestea, în cel mai rău caz, în cazul coliziunilor sau al necesității de a extinde array-ul intern, complexitatea poate crește temporar până la O(n), unde n este numărul de elemente.

Exemplu în Swift:

var dict = [String: Int]()
dict["key"] = 42 // Adăugare în O(1) în medie