Qual é o pior tempo de execução do método add() para ArrayList?

Tempo amortizado constante O(1).

Na maioria dos casos, add() é executado em tempo constante, pois o novo elemento é simplesmente adicionado ao final do array interno existente.

O pior caso ocorre quando a capacidade do array interno é atingida. Nesse caso, ArrayList cria um novo array maior (geralmente 1,5 vezes maior que o atual), copia todos os elementos do array antigo para o novo e então adiciona o novo elemento. Essa operação de cópia leva um tempo proporcional ao número atual de elementos (N), resultando em uma complexidade de tempo O(N).

No entanto, como essas mudanças de tamanho ocorrem raramente e são distribuídas ao longo de muitas chamadas a add(), o tempo médio de execução de add() (amortizado) permanece constante.