Em que situações a adição de um elemento ao final de um ArrayList pode ter uma complexidade de tempo O(n)?

A adição de um elemento ao final do ArrayList geralmente tem uma complexidade de tempo amortizada de O(1), mas em alguns casos pode ser O(n). Isso ocorre quando o array interno que armazena os elementos está cheio e precisa ser expandido.

Ao adicionar um novo elemento:

• Se houver espaço, o elemento é simplesmente adicionado — O(1).
• Se não houver espaço, um novo array de tamanho maior é criado (geralmente 1,5 a 2 vezes maior), e todos os elementos existentes são copiados para o novo array — essa operação é O(n).

Portanto, adicionar um elemento pode ter uma complexidade de tempo O(n) exatamente no momento de expandir o array interno.