Como analisar a complexidade de qualquer código

Nesta aula você aprende as quatro regras que resolvem 95% das análises. A partir daqui, toda complexidade que aparecer no curso vem com a justificativa — e você vai conseguir conferir cada uma.

Regra 1 — Blocos em sequência: soma (e fica o maior)

Se o código faz uma coisa e depois faz outra, os custos se somam:

for x in nums:        # O(n)
    ...
for x in nums:        # O(n) de novo
    ...

Total: O(n + n) = O(2n) = O(n). Dois loops separados continuam lineares! Esse é um erro clássico: ver dois for e gritar "O(n²)". Só é quadrático se um estiver dentro do outro.

Se os blocos têm custos diferentes, vence o maior: ordenar O(n log n) e depois percorrer O(n) dá O(n log n + n) = O(n log n).

Regra 2 — Loops aninhados: multiplica

Se para cada volta do loop de fora o loop de dentro roda inteiro, o custo multiplica:

for i in range(n):        # roda n vezes...
    for j in range(n):    # ...e cada vez custa n
        ...               # total: n × n = O(n²)

A justificativa é literal: o corpo executa n × n vezes. E se o loop de dentro for range(i + 1, n)? Ele roda n-1, depois n-2, ... até 1 vez. A soma 1 + 2 + ... + n = n(n+1)/2 ≈ n²/2 — a constante ½ cai e continua O(n²).

Cuidado com o disfarce: o que multiplica é "quantas vezes o de dentro roda", não a quantidade de for no texto. Um loop interno que roda sempre 10 vezes (fixas, sem depender de n) dá n × 10 = O(n).

Regra 3 — Cortar pela metade: log

Se a cada passo o problema divide (em vez de diminuir de 1 em 1), o número de passos é logarítmico:

while n > 1:
    n = n // 2    # 1.000.000 → 500.000 → 250.000 → ... → 1

Quantas vezes dá para dividir 1.000.000 por 2 até chegar em 1? Cerca de 20 (porque 2²⁰ ≈ 1 milhão). Isso é log₂(n) — e escrevemos O(log n). É a assinatura da busca binária, que você verá na seção Binary.

E o O(n log n)? É um trabalho O(log n) repetido n vezes (ou O(n) repetido log n vezes) — o custo dos bons algoritmos de ordenação. Regra prática do curso: "usei sort? Já estou pagando O(n log n)".

Regra 4 — Custo escondido das operações prontas

Toda chamada de função tem um custo, mesmo quando é uma linha só:

O erro mais comum de análise é esquecer esses custos: um x in lista dentro de um loop é um O(n) dentro de um O(n) — regra 2: O(n²) disfarçado de uma linha.

Colocando as regras para trabalhar

Analise o código abaixo antes de rodar. Qual o Big-O de cada função? Use as regras e depois confira com a contagem de passos.

Gabarito: misterio_a é O(n log n) — o sort domina a sequência (regra 1 + regra 4). misterio_b é O(n log n) — um log n dentro de um loop n (regras 2 e 3).

O método em 3 perguntas

Diante de qualquer código, pergunte:

1. Quantas vezes cada loop roda? (n? metade a cada vez = log n? fixo = constante?)
2. Estão aninhados (multiplica) ou em sequência (soma, fica o maior)?
3. Alguma operação "de uma linha" tem custo escondido? (sort, in de lista, min/max...)

Resumo

• Sequência soma (fica o termo maior); aninhamento multiplica.
• Dividir pela metade = O(log n); sort = O(n log n).
• Operações de "uma linha" têm custo escondido — in de lista é O(n).
• Análise é responder: quantas vezes cada pedaço roda, e por quê.

Na próxima aula: a outra metade da análise — memória — e o quiz que fecha os fundamentos.