Qual é a complexidade assintótica da pesquisa numa lista com um ciclo aninhado?

Se tiver uma lista e realizar uma pesquisa usando um ciclo aninhado (por exemplo, dois ciclos aninhados sobre a mesma lista), a complexidade assintótica dessa pesquisa geralmente será O(n²), onde n é o tamanho da lista.

Isso acontece porque o ciclo externo é executado n vezes, e para cada passagem, o ciclo interno também é executado n vezes, totalizando n * n = n² operações.

Exemplo:

for i in range(len(lst)):
    for j in range(len(lst)):
        if lst[i] == lst[j]:
            # alguma operação