Худшее время работы метода add() для ArrayList - это O(n), где n - это размер списка. Это происходит из-за того, что массивы в Java имеют фиксированный размер, и при добавлении нового элемента внутренний массив может переполниться. В этом случае ArrayList создает новый массив большего размера, копирует все существующие элементы в новый массив и только затем добавляет новый элемент в конец. Этот процесс называется "расширением емкости" (capacity expansion) и может занять значительное время, особенно если список содержит много элементов. Если такая операция выполняется часто, то время выполнения метода add() может быть довольно высоким...