Qual è la complessità temporale dell'operazione di inserimento di un nuovo elemento in un array?

L'inserimento di un nuovo elemento in un array ha una complessità temporale di O(n) nel caso peggiore, dove n è il numero di elementi nell'array.

Il motivo è che l'array ha una dimensione fissa, e per inserire un elemento nel mezzo o all'inizio, è necessario spostare tutti gli elementi successivi di una posizione verso destra. Se l'inserimento avviene alla fine e c'è spazio libero, l'operazione può essere O(1).

Esempio:

• Inserimento alla fine con spazio disponibile: O(1)
• Inserimento all'inizio o nel mezzo: O(n) a causa dello spostamento degli elementi

Nei array dinamici (ad esempio, ArrayList in Java), quando l'array si riempie, si effettua una copia in un nuovo array di dimensione maggiore, il che richiede anch'esso O(n) tempo.