Kaip nustatyti laiko sudėtingumą operacijai įterpti elementą į vidurį duomenų struktūros, atstovaujančios žodyną?

Elemento įterpimas į duomenų struktūrą, kuri vaizduoja žodyną, priklauso nuo konkrečios žodyno įgyvendinimo. Standartiniuose žodynuose (pvz., Dictionary Swift arba NSDictionary Objective-C) elementai neturi iš anksto nustatyto tvarkos indekso, todėl sąvoka "įterpti į vidurį" nėra tiesiogiai taikoma.

Jei kalbame apie duomenų struktūrą, kuri saugo poras raktas-reikšmė tvarkinga (pvz., porų masyvas), tada įterpimas į vidurį reikalauja perkelti visus vėlesnius elementus, kas sudaro laiko sudėtingumą O(n), kur n – elementų skaičius po įterpimo pozicijos.

Hash lentelėse (žodynų pagrinde) įterpimas dažniausiai vyksta amortizuotu laiku O(1), bet be "vidurio" sąvokos.

Taigi, jei duomenų struktūra yra tvarkinga ir įgyvendinta kaip masyvas, įterpimas į vidurį yra O(n). Jei tai hash lentelė, įterpimas yra O(1), bet "vidurio" sąvoka nėra taikoma.