Lug'atga yangi element qo'shishning vaqt murakkabligi qanday?

Yangi elementni lug'atga qo'shishning vaqt murakkabligi (masalan, Swift'dagi Dictionary yoki Objective-C'dagi NSMutableDictionary) odatda O(1) bo'lib, bu hash jadvali asosida amalga oshirilgani uchun, hash hisoblash va joylashtirish doimiy vaqtda amalga oshadi.

Ammo, eng yomon holatda, koliziyalar yoki ichki massivni kengaytirish zarur bo'lsa, murakkablik vaqtincha O(n) ga oshishi mumkin, bu yerda n elementlar soni.

Swift'da misol:

var dict = [String: Int]()
dict["key"] = 42 // O'rtacha O(1) qo'shish