Time complexity of contains(Object o), in an ArrayList of Objects

O(n)

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html

it's O(n) for ArrayList

its O(n). contains(Object o) is implemented on indexOf() which takes O(n). So complexity of contains(Object o) is defensively O(n)

Here are some other if you need:

add() - O(1)
add(index, element) – O(n)
get() – O(1)
set() – O(1)
remove() –  (n)
indexOf()` – O(n)