Aká je časová zložitosť operácie pridania prvku do dynamického poľa?

Pridanie prvku do dynamického poľa má zvyčajne amortizovanú časovú zložitosť O(1).

Vysvetlenie:

• Ak je v poli voľné miesto, prvok sa pridá za konštantný čas.
• Ak miesto nie je, pole alokuje nový väčší blok pamäte (zvyčajne dvojnásobný), skopíruje staré prvky a pridá nový.

Hoci operácia rozšírenia trvá O(n), nestáva sa často, takže priemerná (amortizovaná) zložitosť pridania zostáva O(1).

Príklad v Go s rezmi:

var arr []int
arr = append(arr, 10) // pridanie prvku

append automaticky rozšíri rez, ak je to potrebné.