Как говорится в заголовке, мне интересно, какая временная сложность метода contains() для ArrayList.
Сложность времени содержит (Object o), в ArrayList объектов
Ответ 1
O(n)
Операции
size
,isEmpty
,get
,set
,iterator
иlistIterator
выполняются в постоянное время. Операцияadd
выполняется в режиме амортизированного постоянного времени, то есть для добавления n элементов требуется время O (n). Все остальные операции выполняются в линейном времени (грубо говоря). Постоянный коэффициент невысок по сравнению с константой для реализации LinkedList.
http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html
Ответ 2
it O (n) для ArrayList