¿Cuál es la complejidad temporal de la operación de agregar un elemento al final de un array de tipo ArrayList?

La complejidad temporal de agregar un elemento al final de un array de tipo ArrayList en promedio es O(1) — tiempo amortizado constante.

Esto sucede porque ArrayList almacena los elementos en un array de tamaño fijo. Cuando agregamos un elemento, si hay espacio libre en el array, simplemente se coloca en la siguiente posición.

Sin embargo, si el array está lleno, se realiza una operación de expansión — se crea un nuevo array de mayor tamaño y todos los elementos se copian en él. Esta operación toma O(n) tiempo, donde n es la cantidad de elementos.

Ejemplo:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Cuando se alcanza la capacidad del array, se realiza una expansión — O(n)

Por lo tanto, la complejidad media de la adición es — O(1), pero en el peor caso — O(n).