Qual é a complexidade temporal da operação de adicionar um elemento ao final de um array do tipo ArrayList?

A complexidade temporal de adicionar um elemento ao final de um array do tipo ArrayList em média é O(1) — tempo amortizado constante.

Isto acontece porque o ArrayList armazena os elementos num array de tamanho fixo. Quando adicionamos um elemento, se houver espaço livre no array, o elemento é simplesmente colocado na próxima posição.

No entanto, se o array estiver cheio, ocorre uma operação de expansão — é criado um novo array de maior tamanho, e todos os elementos são copiados para ele. Esta operação leva O(n) tempo, onde n é o número de elementos.

Exemplo:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Quando a capacidade do array é atingida, ocorre uma expansão — O(n)

Assim, a complexidade média de adição é — O(1), mas no pior caso — O(n).