Mekkora az aszimptotikus keresési összetettség egy listában, amelyben egymásba ágyazott ciklus van?

Ha van egy listád, és egy beágyazott ciklust használsz kereséshez (például két beágyazott ciklus ugyanazon lista fölött), akkor az ilyen keresés aszimptotikus összetettsége általában O(n²), ahol n a lista mérete.

Ez azért van, mert a külső ciklus n-szer fut, és minden futásnál a belső ciklus is n-szer fut, összesen n * n = n² műveletet eredményezve.

Példa:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # valamilyen művelet