Jak určit časovou složitost operace vložení prvku do středu datové struktury představující slovník?

Vložení prvku do středu datové struktury představující slovník závisí na konkrétní implementaci slovníku. U standardních slovníků (například Dictionary ve Swiftu nebo NSDictionary v Objective-C) prvky nemají uspořádaný index, takže pojem "vložit do středu" se přímo neuplatní.

Pokud se jedná o datovou strukturu, která ukládá páry klíč-hodnota v uspořádaném pořadí (například pole párů), pak vložení do středu vyžaduje posun všech následujících prvků, což má časovou složitost O(n), kde n je počet prvků po pozici vložení.

U hash tabulek (základ slovníků) je vložení obvykle prováděno v amortizovaném čase O(1), ale bez pojmu "střed".

Pokud je datová struktura seřazená a implementovaná jako pole, je vložení do středu O(n). Pokud je to hash tabulka, je vložení O(1), ale pojem "střed" není použitelný.