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

Поиск элемента в списке (list) в Python имеет линейную сложность O(n), так как это операция последовательного перебора.

Пример:

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

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

my_set = {1, 2, 3, 4, 5}  
if 3 in my_set:  # O(1) — мгновенный доступ  
    print("Found")