Амортизированное константное время O(1).
В большинстве случаев add() выполняется за константное время, так как новый элемент просто добавляется в конец существующего внутреннего массива.
Наихудший случай возникает при достижении вместимости внутреннего массива. В этом случае ArrayList создает новый, больший массив (обычно в 1.5 раза больше текущего), копирует в него все элементы из старого массива, а затем добавляет новый элемент. Эта операция копирования занимает время, пропорциональное текущему количеству элементов (N), что приводит к временной сложности O(N).
Однако, поскольку такие изменения размера происходят редко и распределены по множеству вызовов add(), среднее время выполнения add() (амортизированное) остается константным.