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

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

my_list = [1, 2, 3, 4, 5]
print(3 in my_list)  # O(n)

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