Care este complexitatea asimptotică a căutării într-o listă cu un ciclu imbricat?

Dacă aveți o listă și efectuați o căutare folosind un ciclu imbricat (de exemplu, două cicluri imbricate pe aceeași listă), complexitatea asimptotică a acestei căutări va fi de obicei O(n²), unde n este dimensiunea listei.

Acest lucru se întâmplă deoarece ciclul exterior se execută de n ori, iar pentru fiecare trecere, ciclul interior se execută și el de n ori, rezultând în total n * n = n² operații.

Exemplu:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # o operație