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

Проверка вхождения элемента в список (element in list) в Python имеет временную сложность O(n), где n — длина списка. Это связано с тем, что в худшем случае необходимо пройти все элементы списка для проверки наличия искомого элемента.

Пример:

my_list = [1, 2, 3, 4, 5]
print(3 in my_list)  # O(n) - линейный поиск

Если требуется частая проверка вхождения, лучше использовать множество (set), где операция in выполняется за O(1) (в среднем случае), но требует дополнительной памяти и не сохраняет порядок элементов.