Aká je úroveň časovej zložitosti operácie pridania prvku na koniec poľa pomocou slice?

V jazyku Go má operácia pridania prvku na koniec slice (append) amortizovanú časovú zložitosť O(1).

Vysvetlenie:

• Ak má slice dostatočnú kapacitu (capacity), pridanie prvku je jednoduché zápisom na nasledujúci voľný index — ide o operáciu v konštantnom čase.

• Ak kapacita nestačí, alokuje sa nový väčší poľ, staré prvky sa skopírujú a pridá sa nový — táto operácia trvá O(n), kde n je aktuálna veľkosť slice.

Avšak, pretože takéto redistribúcie sa neudejú pri každom pridávaní, ale iba periodicky, priemerná (amortizovaná) zložitosť pridávania zostáva O(1).