Сложность времени содержит (Object o), в ArrayList объектов

Как говорится в заголовке, мне интересно, какая временная сложность метода contains() для 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