Sözlükü təmsil edən məlumat strukturasının ortasına element əlavə etmə əməliyyatının vaxt mürəkkəbliyini necə müəyyən etmək olar?

Sözlükü təmsil edən məlumatlar strukturunun ortasına element yerləşdirmək, sözlükün konkret tətbiqinə bağlıdır. Standart sözlüklərdə (məsələn, Swift-də Dictionary və ya Objective-C-də NSDictionary) elementlər sıralanmış indeksə malik deyil, ona görə də "ortaya yerləşdirmək" anlayışı birbaşa tətbiq edilmir.

Əgər məlumatlar strukturu açar-dəyər cütlərini sıralı formada saxlayırsa (məsələn, cütlər massivində), onda ortaya yerləşdirmək üçün bütün sonrakı elementləri hərəkət etdirmək lazımdır ki, bu da vaxt mürəkkəbliyi O(n)-ə bərabərdir, burada n yerləşdirmə mövqeyindən sonra olan elementlərin sayıdır.

Hash cədvəllərində (sözlüklərin əsasını təşkil edən) yerləşdirmə adətən amortizasiya olunmuş O(1) vaxtda həyata keçirilir, lakin "orta" anlayışı yoxdur.

Beləliklə, əgər məlumatlar strukturu sıralanıb və massiv kimi tətbiq olunubsa, ortaya yerləşdirmə O(n). Əgər bu hash cədvəlidirsə, yerləşdirmə O(1), lakin "orta" anlayışı tətbiq edilmir.