Как оценивается производительность операции поиска элемента в ArrayList?

В ArrayList поиск элемента по значению (например, с помощью метода contains или indexOf) выполняется путём последовательного перебора элементов с начала до конца. Это означает, что в худшем случае время поиска — O(n), где n — количество элементов в списке. Такой подход обусловлен тем, что ArrayList не хранит элементы в отсортированном виде и не использует хеширование для поиска. Если же известен индекс, доступ к элементу происходит за O(1).