Kāda ir laika sarežģītība, pievienojot jaunu elementu vārdnīcai?

Vārdu krājuma (piemēram, Swift Dictionary vai Objective-C NSMutableDictionary) jauna elementa pievienošanas laika sarežģītība parasti ir O(1) vidēji. Tas ir tāpēc, ka vārdnīca ir īstenota, balstoties uz hašēšanas tabulu, kur haša aprēķins un ievietošana notiek konstanta laika.

Tomēr sliktākajā gadījumā, sastopoties ar kolīzijām vai nepieciešamību paplašināt iekšējo masīvu, sarežģītība pagaidu var palielināties līdz O(n), kur n ir elementu skaits.

Piemērs Swift:

var dict = [String: Int]()
dict["key"] = 42 // Vidēji O(1) pievienošana