Qual è il peggior tempo di esecuzione del metodo add() per ArrayList?

Tempo amortizzato costante O(1).

Nella maggior parte dei casi, add() viene eseguito in tempo costante, poiché il nuovo elemento viene semplicemente aggiunto alla fine dell'array interno esistente.

Il caso peggiore si verifica quando si raggiunge la capacità dell'array interno. In questo caso, ArrayList crea un nuovo array più grande (di solito 1,5 volte più grande di quello attuale), copia tutti gli elementi dal vecchio array al nuovo e poi aggiunge il nuovo elemento. Questa operazione di copia richiede un tempo proporzionale al numero attuale di elementi (N), portando a una complessità temporale O(N).

Tuttavia, poiché tali cambiamenti di dimensione si verificano raramente e sono distribuiti su molte chiamate a add(), il tempo medio di esecuzione di add() (amortizzato) rimane costante.