Jak określić złożoność czasową operacji wstawiania elementu w środek struktury danych reprezentującej słownik?

Wstawianie elementu w środku struktury danych reprezentującej słownik zależy od konkretnej implementacji słownika. W standardowych słownikach (np. Dictionary w Swift lub NSDictionary w Objective-C) elementy nie mają uporządkowanego indeksu, więc pojęcie "wstawić w środku" nie ma bezpośredniego zastosowania.

Jeśli chodzi o strukturę danych, która przechowuje pary klucz-wartość w uporządkowany sposób (np. tablica par), to wstawianie w środek wymaga przesunięcia wszystkich kolejnych elementów, co daje złożoność czasową O(n), gdzie n to liczba elementów po pozycji wstawienia.

W tablicach mieszających (podstawie słowników) wstawianie zwykle odbywa się w czasie amortyzowanym O(1), ale bez pojęcia "środka".

Zatem, jeśli struktura danych jest uporządkowana i zaimplementowana jako tablica, wstawianie w środek to O(n). Jeśli to tablica mieszająca, to wstawianie to O(1), ale pojęcie "środka" nie ma zastosowania.