¿Cuál es la complejidad asintótica de la búsqueda en una lista con un ciclo anidado?

Si tienes una lista y realizas una búsqueda mediante un ciclo anidado (por ejemplo, dos ciclos anidados sobre la misma lista), la complejidad asintótica de dicha búsqueda generalmente será O(n²), donde n es el tamaño de la lista.

Esto sucede porque el ciclo externo se ejecuta n veces, y para cada iteración, el ciclo interno también se ejecuta n veces, en total n * n = n² operaciones.

Ejemplo:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # alguna operación