Care este cel mai rău timp de execuție al metodei add() pentru ArrayList?

Timp amortizat constant O(1).

În cele mai multe cazuri, add() se execută în timp constant, deoarece noul element este pur și simplu adăugat la sfârșitul array-ului intern existent.

Cazul cel mai rău apare atunci când se atinge capacitatea array-ului intern. În acest caz, ArrayList creează un nou array mai mare (de obicei de 1,5 ori mai mare decât cel actual), copiază toate elementele din vechiul array în cel nou și apoi adaugă noul element. Această operație de copiere durează un timp proporțional cu numărul actual de elemente (N), ceea ce duce la o complexitate temporală O(N).

Totuși, deoarece astfel de modificări de dimensiune apar rar și sunt distribuite pe mai multe apeluri add(), timpul mediu de execuție al add() (amortizat) rămâne constant.