Wat is de tijdcomplexiteit van de operatie om een element toe te voegen aan een dynamische array?

Het toevoegen van een element aan een dynamische array heeft meestal een geamortiseerde tijdscomplexiteit van O(1).

Uitleg:

• Als er vrije ruimte in de array is, wordt het element in constante tijd toegevoegd.
• Als er geen ruimte is, reserveert de array een nieuw groter geheugenblok (meestal twee keer zo groot), kopieert de oude elementen en voegt het nieuwe toe.

Hoewel de uitbreidingsoperatie O(n) kost, gebeurt deze niet vaak, dus de gemiddelde (geamortiseerde) complexiteit van toevoegen blijft O(1).

Voorbeeld in Go met slices:

var arr []int
arr = append(arr, 10) // element toevoegen

append zal de slice automatisch uitbreiden indien nodig.