Jaká je asymptotická složitost hledání v seznamu s vloženým cyklem?

Pokud máte seznam a provádíte hledání pomocí vnořeného cyklu (například dva vnořené cykly nad stejným seznamem), pak bude asymptotická složitost takového hledání obvykle O(n²), kde n je velikost seznamu.

K tomu dochází, protože vnější cyklus se provádí nkrát a pro každý průchod se vnitřní cyklus také provádí nkrát, což dohromady dává n * n = n² operací.

Příklad:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # nějaká operace