Koja je vremenska složenost operacije umetanja novog elementa u niz?

Dodavanje novog elementa u niz ima vremensku složenost O(n) u najgorem slučaju, gde je n broj elemenata u nizu.

Razlog je taj što niz ima fiksnu veličinu, i za umetanje elementa u sredinu ili na početak, potrebno je pomeriti sve naredne elemente za jednu poziciju udesno. Ako umetanje vrši na kraj i postoji slobodno mesto, operacija može biti O(1).

Primer:

• Umetanje na kraj uz dostupno mesto: O(1)
• Umetanje na početak ili u sredinu: O(n) zbog pomeranja elemenata

U dinamičkim nizovima (npr. ArrayList u Javi), kada se niz napuni, vrši se kopiranje u novi niz većeg kapaciteta, što takođe zahteva O(n) vremena.