Jaka jest złożoność czasowa operacji dodawania elementu do dynamicznej tablicy?

Dodanie elementu do dynamicznej tablicy zazwyczaj ma amortyzowaną złożoność czasową O(1).

Wyjaśnienie:

• Jeśli w tablicy jest dostępne miejsce, element jest dodawany w czasie stałym.
• Jeśli miejsca nie ma, tablica przydziela nowy większy blok pamięci (zwykle dwa razy większy), kopiuje stare elementy i dodaje nowy.

Chociaż operacja rozszerzenia zajmuje O(n), nie zdarza się często, więc średnia (amortyzowana) złożoność dodawania pozostaje O(1).

Przykład w Go z użyciem slices:

var arr []int
arr = append(arr, 10) // dodanie elementu

append automatycznie rozszerzy slice w razie potrzeby.