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

Если у вас есть список и вы выполняете поиск с помощью вложенного цикла (например, два вложенных цикла по одному и тому же списку), то асимптотическая сложность такого поиска обычно будет O(n²), где n — размер списка.

Это происходит потому, что внешний цикл выполняется n раз, и для каждого прохода внутренний цикл тоже выполняется n раз, в итоге n * n = n² операций.

Пример:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # какая-то операция