Come viene determinata la complessità temporale nell'aggiunta di un elemento a ArrayList?

La complessità temporale di aggiunta di un elemento a ArrayList è generalmente ammortizzata a O(1). Ciò è dovuto al fatto che:

• Se l'array interno di ArrayList ha spazio libero, il nuovo elemento viene semplicemente scritto nella posizione successiva — l'operazione richiede un tempo costante O(1).
• Se l'array interno è pieno, viene effettuata un'espansione: viene creato un nuovo array di dimensione maggiore e tutti gli elementi vengono copiati lì. Questa operazione richiede O(n), dove n è la dimensione attuale della lista.

Tuttavia, l'espansione non avviene ad ogni aggiunta, ma periodicamente, quindi la complessità media (ammortizzata) dell'aggiunta rimane O(1).

Esempio:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // Ammortizzato O(1)