Jaki jest najgorszy czas wykonania metody add() dla ArrayList?

Amortyzowany czas stały O(1).

W większości przypadków add() wykonuje się w czasie stałym, ponieważ nowy element jest po prostu dodawany na koniec istniejącej tablicy wewnętrznej.

Najgorszy przypadek występuje, gdy osiągnięta zostanie pojemność wewnętrznej tablicy. W tym przypadku ArrayList tworzy nową, większą tablicę (zwykle 1,5 raza większą od obecnej), kopiuje wszystkie elementy ze starej tablicy do nowej, a następnie dodaje nowy element. Ta operacja kopiowania zajmuje czas proporcjonalny do aktualnej liczby elementów (N), co prowadzi do złożoności czasowej O(N).

Jednakże, ponieważ takie zmiany rozmiaru zdarzają się rzadko i są rozłożone na wiele wywołań add(), średni czas wykonania add() (amortyzowany) pozostaje stały.