Как определить временную сложность операции поиска элемента в коллекции, представленной списком?

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

Пример: поиск значения x в списке lst реализуется через перебор:

lst = [1, 3, 5, 7, 9]
x = 7
found = False
for item in lst:
    if item == x:
        found = True
        break

Если список не отсортирован, более эффективных способов поиска без дополнительной структуры данных нет. Если список отсортирован, можно использовать бинарный поиск с временной сложностью O(log n).