Hogyan határozható meg egy szótárat reprezentáló adatszerkezet közepébe történő elem beszúrásának időbeli összetettsége?

Egy elem beszúrása egy olyan adatszerkezet közepébe, amely egy szótárat képvisel, a szótár konkrét megvalósításától függ. A standard szótárakban (például a Swift Dictionary-jében vagy az Objective-C NSDictionary-jében) az elemeknek nincs rendezett indexük, így a "középre beszúrás" fogalma nem alkalmazható közvetlenül.

Ha olyan adatszerkezetről van szó, amely kulcs-érték párokat tárol rendezett formában (például párok tömbje), akkor a középre való beszúrás minden további elemet eltolást igényel, ami időbeli komplexitást eredményez O(n), ahol n a beszúrási pozíció utáni elemek száma.

A hash-táblákban (amelyek a szótárak alapját képezik) a beszúrás általában amortizált O(1) időben történik, de a "közép" fogalma nem értelmezhető.

Tehát, ha az adatszerkezet rendezett és tömbként van megvalósítva, a középre való beszúrás O(n). Ha hash-tábla, akkor a beszúrás O(1), de a "közép" fogalma nem alkalmazható.