¿En qué situaciones la adición de un elemento al final de un ArrayList puede tener una complejidad temporal de O(n)?

La adición de un elemento al final de ArrayList generalmente tiene una complejidad temporal amortizada de O(1), pero en algunos casos puede ser O(n). Esto ocurre cuando el array interno que almacena los elementos está lleno y es necesario ampliarlo.

Al agregar un nuevo elemento:

• Si hay espacio, simplemente se añade — O(1).
• Si no hay espacio, se crea un nuevo array de mayor tamaño (generalmente 1.5-2 veces mayor), y todos los elementos existentes se copian en el nuevo array — esta operación es O(n).

Por lo tanto, agregar un elemento puede tener una complejidad temporal de O(n) justo en el momento de ampliar el array interno.