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

Временная сложность операции поиска элемента в ArrayList зависит от того, как именно происходит поиск:

• Если речь о поиске по индексу (например, get(index)), то операция выполняется за O(1), так как ArrayList реализован на основе массива и доступ по индексу мгновенный.

• Если же нужно найти элемент по значению (например, contains(element) или indexOf(element)), то ArrayList перебирает элементы последовательно, поэтому временная сложность будет O(n), где n — количество элементов в списке.

Пример поиска по значению:

ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("cherry");

boolean found = list.contains("banana"); // O(n)