Qual é a complexidade temporal das operações de busca e adição de elementos no ArrayList?

As operações de adicionar um elemento ao final de uma ArrayList são realizadas em tempo amortizado O(1), pois quando é necessário expandir o array interno, o tempo pode aumentar, mas em média a adição é rápida.

A busca de um elemento por índice (o método get(int index)) ocorre em tempo O(1), pois ArrayList é implementado com base em um array.

No entanto, procurar um elemento pelo valor (por exemplo, contains() ou indexOf()) requer percorrer os elementos e leva tempo O(n), onde n é o número de elementos na lista.