Какое худшее время работы метода contains() для элемента, который есть в ArrayList

Худшее время — O(N). Метод contains() в ArrayList выполняет линейный поиск по внутреннему массиву, сравнивая каждый элемент через equals().

Хотя ArrayList основан на массиве с произвольным доступом, для поиска по значению (а не по индексу) это не дает преимущества — массив не отсортирован, поэтому бинарный поиск неприменим. В худшем случае искомый элемент расположен в конце массива, и метод проверит все N элементов.

На собеседовании: ответ одинаковый для ArrayList и LinkedList — O(N). Уточните, что произвольный доступ по индексу в ArrayList O(1), но поиск по значению — всегда линейный.