Qual è la complessità temporale dell'operazione di aggiunta di un elemento a un array dinamico?

L'aggiunta di un elemento a un array dinamico ha generalmente una complessità temporale ammortizzata di O(1).

Spiegazione:

• Se c'è spazio libero nell'array, l'elemento viene aggiunto in tempo costante.
• Se non c'è spazio, l'array assegna un nuovo blocco di memoria più grande (di solito il doppio), copia gli elementi vecchi e aggiunge il nuovo.

Anche se l'operazione di espansione richiede O(n), non avviene frequentemente, quindi la complessità media (ammortizzata) dell'aggiunta rimane O(1).

Esempio in Go con slice:

var arr []int
arr = append(arr, 10) // aggiunta di un elemento

append espanderà automaticamente il slice se necessario.