Koja je asimptotska složenost pretraživanja u listi sa ugnježdenom petljom?

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