Ποια είναι η ασυμπτωτική πολυπλοκότητα της αναζήτησης σε μια λίστα με ενσωματωμένο βρόχο;

Αν έχετε μια λίστα και πραγματοποιείτε μια αναζήτηση χρησιμοποιώντας έναν εμφωλευμένο βρόχο (π.χ., δύο εμφωλευμένους βρόχους στην ίδια λίστα), η ασυμπτωτική πολυπλοκότητα αυτής της αναζήτησης θα είναι συνήθως 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]:
            # κάποια λειτουργία