Koja je vremenska složenost operacije dodavanja elementa u dinamički niz?

Dodavanje elementa u dinamički niz obično ima amortizovanu vremensku složenost O(1).

Objašnjenje:

• Ako u nizu postoji slobodno mesto, element se dodaje u konstantnom vremenu.
• Ako nema mesta, niz alocira novi veći blok memorije (obično duplo veći), kopira stare elemente i dodaje novi.

Iako operacija proširenja traje O(n), ona se ne dešava često, pa je prosečna (amortizovana) složenost dodavanja i dalje O(1).

Primer u Go-u sa rezovima:

var arr []int
arr = append(arr, 10) // dodavanje elementa

append će automatski proširiti rezim ako je potrebno.