Jaká je úroveň časové složitosti operace přidání prvku na konec pole pomocí slice?

V jazyce Go má operace přidání prvku na konec slice (append) amortizovanou časovou složitost O(1).

Vysvětlení:

• Pokud má slice dostatečnou kapacitu (capacity), přidání prvku je jednoduché zápisem na následující volný index — jedná se o operaci v konstantním čase.

• Pokud kapacita nestačí, alokuje se nový větší pole, staré prvky se zkopírují a přidá se nový prvek — tato operace trvá O(n), kde n je aktuální velikost slice.

Nicméně, protože takové přerozdělení nedochází při každém přidání, ale pouze periodicky, průměrná (amortizovaná) složitost přidání zůstává O(1).