Anatomia da Notação Big‑O: Entenda a Complexidade de Algoritmos

Visão Rápida — A notação Big‑O é uma forma de medir quanto tempo e memória seu código pode consumir à medida que a entrada cresce. Dominar Big‑O é saber identificar padrões de custo para tomar decisões informadas.

1. Por que Big‑O importa?

• Escalabilidade previsível — evita surpresas quando n passa de 1 k para 10 M.
• Linguagem comum — candidatos e entrevistadores discutem soluções usando Big‑O.
• Comparação objetiva — decide rapidamente qual implementação vale manter e otimizar.

2. Trindade Assintótica

Regra de ouro: use Big‑O para garantir que seu algoritmo nunca excede determinado custo.

3. Casos de Complexidade

• Pior caso (Big O) — entrada que provoca máximo de trabalho.
• Caso médio (Θ) — desempenho típico para entradas aleatórias.
• Melhor caso (Ω) — raramente decisivo, mas serve de garantia mínima.

4. Como calcular Big‑O passo a passo

1. Mapeie as variáveis de entrada
   Identifique tudo o que pode crescer: n (tamanho do vetor), m (número de arestas), k (profundidade da árvore) – elas vão aparecer nas contas.

2. Marque as operações‑chave
   Conte comparações, atribuções, leituras de memória e chamadas de função que realmente impactam desempenho. Comentários e variáveis auxiliares sem custo assintótico podem ser ignorados.

3. Avalie blocos lineares
   Se dois trechos rodam um após o outro, soma‑se o custo:

   O(n)   // loop A
   O(n^2) // loop B
   

   Resultado → O(n²) porque o termo mais alto domina a soma.

4. Inclua condicionais no pior caso
   Para if / else, some apenas o caminho mais caro:

   if found:          # O(1)
       return
   else:              # O(n)
       linear_search()

   Big‑O = O(n).

5. Multiplique loops aninhados
   Cada loop interno se multiplica pelo externo:

   for (i = 0; i < n; i++)        // n
       for (j = 0; j < m; j++)    // m
           op();                  // 1
   // → O(n · m)
   

   Loops dependentes (‑até j < i) geram progressão aritmética → O(n²/2) = O(n²).

6. Trate recursão como recorrência
   Escreva a equação e resolva via:

   • Árvore de recursão – visualize níveis e conte nós.
   • Teorema Mestre – para T(n) = a T(n/b) + f(n).
   • Substituição – chute a solução e prove por indução.

7. Normalização & descarte de detalhes
   Remova constantes e termos menores:

   3n + 7  → O(n)
   n/2     → O(n)
   log₂n   → O(log n)   // base muda por constante

8. Documente complexidade de espaço
   Analise variáveis alocadas, pilha de recursão e buffers.
   Ex.: Merge Sort usa O(n) extra; Quick Sort in‑place usa O(log n) de pilha.

9. Cheque gargalos de I/O
   Operações de disco/rede podem dominar o tempo de CPU – use Big‑O para CPU e para I/O quando necessário.

10. Valide com experimento rápido
    Use time, perf ou cProfile para confirmar que o comportamento real segue a análise assintótica.

Mini‑exemplo completo

def foo(arr):
    n = len(arr)              # O(1)
    total = 0                 # O(1)

    # Loop externo               => n
    for i in range(n):
        total += arr[i]        # O(1)

        # Loop interno dependente => i
        for j in range(i):     
            total += arr[j]    # O(1)

    return total

Receita:

1. Loops aninhados → soma de série 1 + 2 + … + (n‑1) = n(n‑1)/2 → O(n²).
2. Constantes ignoradas → O(n²) tempo, O(1) espaço.

Dica prática: ao revisar código, escreva o Big‑O no comentário de cada bloco. Isso treina o olhar e facilita code‑review de colegas iniciantes.

5. Tabela de Complexidade de Estruturas

Notas

• Amortizado: tempo médio por operação após muitas operações (caso do array dinâmico).
• k em Bloom Filter indica o nº de funções hash usadas.
• Para tries, O(L) é proporcional ao comprimento da palavra, não ao nº de chaves.

6. Complexidade por Gráfico

Observe como O(n!) explode comparado a O(n log n) — fundamental para escolhas arquiteturais.

7. Exemplos Comentados

Esta seção reúne trechos clássicos de código para ilustrar como cada classe de Big‑O se comporta na prática, tomando como base o artigo “Common Big‑O Notations” da GeeksforGeeks.

7.1 Linear Time — O(n)

bool findElement(int arr[], int n, int key) {
    for (int i = 0; i < n; ++i)
        if (arr[i] == key) return true;
    return false;
}

Executa uma comparação por elemento → cresce linearmente.

7.2 Logarithmic Time — O(log n)

def binary_search(arr, x):
    l, r = 0, len(arr) - 1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] == x:
            return mid
        l, r = (mid + 1, r) if arr[mid] < x else (l, mid - 1)
    return -1

Cada passo descarta metade da entrada → curva logarítmica.

7.3 Quadratic Time — O(n²) (Nested Loops)

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        process(i, j);  // n × n chamadas

Segundo loop roda n vezes para cada volta do primeiro → n².

7.4 Cúbica — O(n³)

void multiply(int A[][N], int B[][N], int C[][N]) {
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            C[i][j] = 0;
            for (int k = 0; k < N; ++k)
                C[i][j] += A[i][k] * B[k][j];
        }
}

Três loops aninhados sobre N → N³ operações.

7.5 Exponencial — O(2ⁿ)

void generateSubsets(int arr[], int n) {
    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int j = 0; j < n; ++j)
            if (mask & (1 << j)) cout << arr[j] << ' ';
        cout << '\n';
    }
}

Há 2ⁿ máscaras possíveis, logo tempo dobra a cada incremento de n.

7.6 Fatorial — O(n!)

void permute(int a[], int l, int r) {
    if (l == r) { print(a, r); return; }
    for (int i = l; i <= r; ++i) {
        swap(a[l], a[i]);
        permute(a, l + 1, r);   // n! permutações
        swap(a[l], a[i]);       // backtrack
    }
}

Número de permutações de n itens é n!, logo tempo explode rapidamente.

7.7 Master Theorem Express

Para recursões da forma T(n) = a T(n/b) + f(n):

Takeaway: Algoritmos acima de O(n log n) já podem se tornar gargalos em escala. Use esta lista como checklist mental na hora de propor soluções ou revisar PRs.

8. Espaço versus Tempo

Big‑O também mede memória.
Merge Sort: O(n log n) tempo, O(n) espaço.
Heap Sort: O(n log n) tempo, O(1) espaço — troca mais comparação por menos RAM.

9. Armadilhas Frequentes

10. Guia de Primeiros Passos (Roadmap Para Iniciantes)

1. Domine uma linguagem (Python/Repl.it é ótimo para feedback rápido).
2. Assista 2 vídeos curtos sobre notação Big‑O (GfG & Computerphile).
3. Analise 5 trechos de código do seu dia‐a‐dia — escreva a complexidade em um caderno.
4. Implemente buscas & sorts do zero (Linear, Binária, Bubble, Merge).
5. Use plataformas gamificadas (HackerRank “Time Complexity” warm‑up).
6. Participe de um contest curto (Codeforces Div. 4) — força você a otimizar rápido.

11. Exercício Guiado

Objetivo: converter um algoritmo ingênuo O(n²) em O(n).

Passo 1 — Código inicial

def count_pairs(arr):
    count = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                count += 1
    return count

Passo 2 — Diagnóstico

Dois loops aninhados → quadrático.

Passo 3 — Otimização com Hash

from collections import Counter
def count_pairs(arr):
    freq = Counter(arr)  # O(n)
    return sum(c * (c-1) // 2 for c in freq.values())  # O(k)

Agora o algoritmo roda em O(n) tempo e O(k) espaço.

12. Mini‑FAQ

Q: Por que ignoramos constantes?
A: Porque em escala grande, fatores proporcionais são irrelevantes frente ao crescimento assintótico.

Q: Big‑O mede tempo de qual operação?
A: Qualquer métrica de custo: CPU, memória, I/O. Especifique qual está analisando.

Q: Preciso decorar todas as classes?
A: Não. Entenda o estilo de curva: constante, log, linear, quadrática, exponencial.

13. Glossário Rápido

• Entrada (n) — quantidade de dados processados.
• Dominante — parte do código que mais contribui para o custo.
• Assintótico — tendência quando n → ∞.
• Overhead — custo extra além da lógica principal (ex.: alocação).

14. Checklist de Entrevista

1. Qual o pior caso?
2. Há estimativa realista do caso médio?
3. Complexidade de espaço?
4. Estrutura de dados alternativa?
5. Pode paralelizar?
6. Trade‑off tempo × memória aceitável?

15. Conclusão

A notação Big‑O é a régua que ajuda a identificar gargalos antes que eles explodam em produção. Com um olhar crítico e prática constante, você passará a reconhecer padrões complexos à primeira vista — e otimizar à segunda.

Desafio Final: Pegue um script seu de ontem, estime Big‑O, depois meça com time. Quanto as estimativas batem com a realidade?