Notação Big O — analisando algoritmos
Como comparar dois algoritmos que resolvem o mesmo problema? Você não compara o tempo em segundos (depende do hardware) — compara como o trabalho cresce conforme a entrada cresce. Essa é a ideia central da notação Big O: ela descreve o comportamento de longo prazo, não o tempo exato.
O que importa é como cresce, não o valor exato
Imagine dois algoritmos para encontrar um nome em uma lista de 1.000 pessoas: um olha todo mundo em sequência (busca linear), outro divide a lista ao meio repetidamente (busca binária). No pior caso, o linear faz 1.000 comparações; o binário faz apenas ~10. Com 1 bilhão de pessoas, o linear faz 1 bilhão de comparações — o binário ainda faz apenas ~30.
Big O captura essa diferença qualitativa. O(n) significa "cresce proporcionalmente a n". O(log n) significa "cresce com o logaritmo de n" — muito mais devagar. A constante de proporcionalidade (2n, 3n, 10n) é ignorada; o que importa é a classe de crescimento.
As curvas de complexidade
Compare visualmente como O(1), O(log n), O(n), O(n log n) e O(n²) crescem. Passe o mouse sobre as curvas para ver os valores exatos.
A tabela que muda tudo
n=10 n=1.000 n=1.000.000 n=10⁹
O(1) 1 1 1 1
O(log n) ~3 ~10 ~20 ~30
O(n) 10 1.000 1.000.000 1 bilhão
O(n log n) ~33 ~10.000 ~20.000.000 ~30 bilhões
O(n²) 100 1.000.000 10¹² 10¹⁸
O(2ⁿ) 1.024 2¹⁰⁰⁰ ≈ 10³⁰⁰ impossível impossível Como contar operações na prática
# Como contar operações para calcular Big O: def busca_linear(lista, alvo): # O(n) for item in lista: # n iterações no pior caso if item == alvo: # O(1) cada return True return False def busca_binaria(lista, alvo): # O(log n) l, r = 0, len(lista) - 1 while l <= r: # divide por 2 a cada passo m = (l + r) // 2 if lista[m] == alvo: return True elif lista[m] < alvo: l = m + 1 else: r = m - 1 return False def par_mais_proximo(lista): # O(n²) melhor = float('inf') for i in range(len(lista)): # n iterações for j in range(i+1, len(lista)): # até n iterações d = abs(lista[i] - lista[j]) if d < melhor: melhor = d return melhor # total: ~n²/2 = O(n²)
Medindo na prática
Mini projeto: implemente busca linear e busca binária em Python. Para n = 100, 1.000, 10.000 e 100.000 elementos, conte o número real de comparações (não use time — conte operações). Plote os resultados em um gráfico. Confirme que linear cresce como n e binária como log₂(n).
Projeto principal: implemente três funções para encontrar o par de elementos mais próximos em uma lista: O(n²) ingênuo (dois loops), O(n log n) (ordena e compara vizinhos), e O(n) usando dicionário. Meça o tempo real com time.perf_counter() para n=1000, 10000, 100000 e observe como a diferença explode.
Desafio extra: estude a complexidade amortizada. Implemente uma lista dinâmica (array que dobra de capacidade). O append individual tem pior caso O(n) (quando redimensiona), mas o custo amortizado é O(1). Explique por que: se começar com capacidade 1 e dobrar a cada resize, após n appends o trabalho total de cópia é 1+2+4+...+n = O(n), logo O(1) por elemento.
Teste sua intuição
Onde você encontra isso
Google e motores de busca
Indexar a web inteira e buscar em milissegundos exige algoritmos muito abaixo de O(n). Índices invertidos permitem buscar uma palavra em O(1): "python" → lista de páginas que contêm essa palavra. A construção do índice é O(n log n) (ordenação), mas a busca é O(1) ou O(k) onde k é o número de resultados.
Entrevistas técnicas de Big Tech
Qualquer entrevista de engenharia em Google, Meta, Amazon ou Microsoft avalia complexidade de tempo e espaço. A resposta "funciona" não é suficiente — você precisa justificar a complexidade. Algoritmos O(n²) falham com n=10⁶. A diferença entre O(n log n) e O(n²) pode ser a diferença entre aceitar e rejeitar um candidato.
Índices de banco de dados
Um SELECT sem índice em uma tabela com 100 milhões de linhas faz full table scan: O(n). Com um índice B-tree, a busca é O(log n) — a diferença entre minutos e milissegundos. Por isso DBAs obsessivamente analisam o EXPLAIN PLAN: cada "Seq Scan" pode esconder um O(n) que vai explodir em produção.