Какое худшее время работы метода add() для ArrayList

Худшее время — O(N). Оно возникает в двух ситуациях: при вставке в начало или середину (сдвиг элементов вправо) и при исчерпании емкости массива (создание нового массива в 1.5 раза больше и копирование всех элементов).

Метод add(E element) (добавление в конец) амортизированно работает за O(1): в большинстве случаев это просто запись в следующую ячейку массива, и лишь изредка — расширение. Метод add(int index, E element) всегда требует сдвига size - index элементов вправо через System.arraycopy().

На собеседовании: ответ — O(N) из-за возможного расширения массива и копирования. Упомяните, что добавление в конец амортизированно O(1) и что для больших вставок полезно задать initialCapacity.