Каква е асимптотичната сложност на търсенето в списък с вложен цикъл?

Ако имате списък и извършвате търсене с помощта на вложен цикъл (например, два вложени цикъла върху същия списък), асимптотичната сложност на такова търсене обикновено ще бъде 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]:
            # някаква операция