Wat is de asymptotische complexiteit van zoeken in een lijst met een geneste lus?

Als je een lijst hebt en je voert een zoekopdracht uit met behulp van een geneste lus (bijvoorbeeld twee geneste lussen over dezelfde lijst), dan is de asymptotische complexiteit van zo'n zoekopdracht meestal O(n²), waarbij n de grootte van de lijst is.

Dit gebeurt omdat de buitenste lus n keer wordt uitgevoerd, en voor elke doorloop wordt de binnenste lus ook n keer uitgevoerd, in totaal n * n = n² operaties.

Voorbeeld:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # een bewerking