Какая сложность алгоритма проверки наличия элемента в списке

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

Пример:

my_list = [1, 2, 3, 4, 5]
if 3 in my_list:  # O(n) - проверка всех элементов
    print("Found")

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