Aká je asymptotická zložitosť vyhľadávania v zozname s vnoreným cyklom?

Ak máte zoznam a vykonávate vyhľadávanie pomocou vnoreného cyklu (napríklad dva vnorené cykly nad rovnakým zoznamom), asymptotická zložitosť takéhoto vyhľadávania bude zvyčajne O(n²), kde n je veľkosť zoznamu.

K tomu dochádza, pretože vonkajší cyklus sa vykoná n-krát, a pri každom prechode sa vnorený cyklus tiež vykoná n-krát, čo dáva celkovo n * n = n² operácií.

Príklad:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # nejaká operácia