Was ist die schlechteste Laufzeit der Methode add() für ArrayList?

Amortisierte konstante Zeit O(1).

In den meisten Fällen wird add() in konstanter Zeit ausgeführt, da das neue Element einfach ans Ende des bestehenden internen Arrays angehängt wird.

Der schlimmste Fall tritt auf, wenn die Kapazität des internen Arrays erreicht ist. In diesem Fall erstellt ArrayList ein neues, größeres Array (in der Regel 1,5-mal so groß wie das aktuelle), kopiert alle Elemente aus dem alten Array in das neue und fügt dann das neue Element hinzu. Diese Kopieroperation dauert proportional zur aktuellen Anzahl der Elemente (N), was zu einer zeitlichen Komplexität von O(N) führt.

Da solche Größenänderungen jedoch selten auftreten und über viele Aufrufe von add() verteilt sind, bleibt die durchschnittliche Ausführungszeit von add() (amortisiert) konstant.