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

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

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

Пример:

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

my_set = {1, 2, 3, 4, 5}  # O(1)
print(3 in my_set)  # True

Вывод: если нужны частые проверки, лучше использовать set или dict.