Jaká je časová složitost operace přidání prvku do dynamického pole?

Přidání prvku do dynamického pole má obvykle amortizovanou časovou složitost O(1).

Vysvětlení:

• Pokud je v poli volné místo, prvek je přidán v konstantním čase.
• Pokud není místo, pole alokuje nový větší blok paměti (obvykle dvojnásobný), zkopíruje staré prvky a přidá nový.

Ačkoli operace rozšíření trvá O(n), nestává se často, takže průměrná (amortizovaná) složitost přidání zůstává O(1).

Příklad v Go s použitím slice:

var arr []int
arr = append(arr, 10) // přidání prvku

append automaticky rozšíří slice podle potřeby.