Jaki jest czasowy wynik operacji wstawiania, wyszukiwania, odczytu i usuwania elementów w tablicy w najgorszym i średnim przypadku?

Dla standardowej tablicy w iOS (np. NSArray lub NSMutableArray) charakterystyki czasowe operacji są mniej więcej następujące:

• Wstawianie:

  • Na koniec tablicy (append): średni i najgorszy przypadek — O(1) amortyzowane (jeśli nie jest wymagana ponowna alokacja pamięci).
  • Na początku lub w środku: O(n), ponieważ konieczne jest przesunięcie elementów.

• Wyszukiwanie (jeśli po indeksie): O(1), ponieważ tablica jest indeksowana.

• Odczyt po indeksie: O(1).

• Usuwanie:

  • Z końca tablicy: O(1).
  • Z początku lub środka: O(n), z powodu przesunięcia elementów.

W związku z tym operacje wstawiania i usuwania w środku lub na początku tablicy mają złożoność liniową, natomiast dostęp i wstawianie/usuwanie na końcu — stałą (amortyzowaną).