Como é determinada a complexidade temporal ao adicionar um elemento ao ArrayList?

A complexidade temporal de adicionar um elemento ao ArrayList é geralmente amortizada a O(1). Isto deve-se ao facto de:

• Se o array interno do ArrayList tiver espaço livre, o novo elemento é simplesmente escrito na próxima posição — a operação leva tempo constante O(1).
• Se o array interno estiver cheio, ocorre uma expansão: é criado um novo array de maior tamanho, e todos os elementos são copiados para lá. Esta operação leva O(n), onde n é o tamanho atual da lista.

No entanto, a expansão não acontece em cada adição, mas periodicamente, pelo que a complexidade média (amortizada) de adicionar permanece O(1).

Exemplo:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // Amortizado O(1)