За какое время выполняется поиск (например, с использованием метода contains) в коллекциях List и Set?

Для List поиск с использованием contains имеет вычислительную сложность O(n), где n — количество элементов в списке. Это связано с тем, что в худшем случае требуется перебрать все элементы списка для определения наличия искомого.

Для Set поиск с использованием contains имеет вычислительную сложность в среднем O(1). Это достигается за счет использования хэш-таблицы для внутреннего хранения элементов. В идеальном случае (хорошая хэш-функция и отсутствие коллизий) поиск занимает постоянное время. В худшем случае (много коллизий) сложность может приближаться к O(n), но это редкость на практике.