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

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

Пример:

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

Для вложенных циклов сложность становится O(n*m), где n и m - размеры списков:

list1 = [1, 2, 3]
list2 = ['a', 'b']
for x in list1:      # O(n)
    for y in list2:  # O(m)
        print(x, y)  # Общая сложность O(n*m)

Операции доступа по индексу в списке (list[i]) имеют сложность O(1), так как списки в Python реализованы как динамические массивы.