In quali situazioni l'aggiunta di un elemento alla fine di un ArrayList può avere una complessità temporale di O(n)?

L'aggiunta di un elemento alla fine di un ArrayList ha generalmente una complessità temporale ammortizzata di O(1), ma in alcuni casi può essere O(n). Questo accade quando l'array interno che memorizza gli elementi è pieno e deve essere espanso.

Quando si aggiunge un nuovo elemento:

• Se c'è spazio, l'elemento viene semplicemente aggiunto — O(1).
• Se non c'è spazio, viene creato un nuovo array di dimensioni maggiori (di solito 1,5-2 volte più grande), e tutti gli elementi esistenti vengono copiati nel nuovo array — questa operazione è O(n).

Pertanto, l'aggiunta di un elemento può avere una complessità temporale di O(n) proprio nel momento in cui si espande l'array interno.