Qual è la complessità temporale dell'operazione di aggiunta di un elemento alla fine di un array di tipo ArrayList?

La complessità temporale di aggiunta di un elemento alla fine di un array di tipo ArrayList in media è O(1) — tempo ammortizzato costante.

Questo accade perché ArrayList memorizza gli elementi in un array di dimensione fissa. Quando aggiungiamo un elemento e c'è spazio nel array, l'elemento viene semplicemente inserito nella cella successiva.

Tuttavia, se l'array è pieno, si verifica un'operazione di espansione — viene creato un nuovo array di dimensione maggiore e tutti gli elementi vengono copiati in esso. Questa operazione richiede O(n) tempo, dove n è il numero di elementi.

Esempio:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Quando si raggiunge la capacità dell'array, si effettua un'espansione — O(n)

Pertanto, la complessità media di aggiunta è — O(1), ma nel caso peggiore — O(n).