Jaka jest asymptotyczna złożoność wyszukiwania na liście z zagnieżdżoną pętlą?

Jeśli masz listę i wykonujesz wyszukiwanie za pomocą zagnieżdżonej pętli (np. dwie zagnieżdżone pętle na tej samej liście), to złożoność asymptotyczna takiego wyszukiwania zwykle będzie wynosić O(n²), gdzie n to rozmiar listy.

Dzieje się tak, ponieważ zewnętrzna pętla wykonuje się n razy, a dla każdego przebiegu wewnętrzna pętla również wykonuje się n razy, co daje łącznie n * n = n² operacji.

Przykład:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # jakaś operacja