¿Cómo se determina la complejidad temporal al agregar un elemento a ArrayList?

La complejidad temporal de agregar un elemento a ArrayList generalmente es amortizadamente O(1). Esto se debe a que:

• Si el array interno de ArrayList tiene espacio libre, el nuevo elemento simplemente se escribe en la siguiente posición — la operación toma tiempo constante O(1).
• Si el array interno está lleno, se realiza una expansión: se crea un nuevo array de mayor tamaño y todos los elementos se copian allí. Esta operación toma O(n), donde n es el tamaño actual de la lista.

Sin embargo, la expansión no ocurre en cada adición, sino periódicamente, por lo que la complejidad media (amortizada) de agregar sigue siendo O(1).

Ejemplo:

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