Como o Custo Cresce

Big O mede como o custo cresce à medida que a entrada cresce. Não o fator constante — a taxa. Dois algoritmos que ambos executam em 'alguns milissegundos' em N=100 podem divergir por um fator de 10.000 em N=10.000, se um executa em tempo O(N) e o outro em O(N²).

As Classes Comuns de Complexidade

O(1) — Constante. Mesmo custo independentemente de N. Exemplos: busca em tabela hash por chave, acesso a array por índice, push/pop em pilha. Dobrar N não muda nada.

O(log N) — Logarítmico. Cada passo reduz pela metade o trabalho restante. Exemplos: busca binária em um array ordenado, consulta espacial BVH em um motor de jogo, operações em árvore binária balanceada. Em N=1.000.000: log₂(1.000.000) ≈ 20 passos.

O(N) — Linear. O custo cresce com a entrada. Exemplos: varredura linear de uma lista, leitura de um arquivo, contagem de itens em uma coleção. Em N=10.000: 10.000 operações.

O(N log N) — Linearítmico. Quase linear, um pouco pior. Exemplos: merge sort, algoritmos eficientes de caminho mais curto (Dijkstra com heap). Em N=10.000: ~133.000 operações.

O(N²) — Quadrático. O custo explode. Exemplos: list.contains() chamado dentro de um loop sobre a mesma lista, bubble sort, comparação ingênua de todos os pares. Em N=1.000: 1.000.000 operações. Em N=10.000: 100.000.000 operações.

O(2^N) — Exponencial. Inviável em qualquer escala significativa. Exemplos: força bruta combinatória, encontrar todos os subconjuntos. Em N=30: mais de 1.000.000.000 operações.

A Escala Que Torna Isso Visível

Comparações para N=10:
O(N):   10
O(N²):  100
razão:  10x

N=1.000 comparações:
O(N):   1.000
O(N²):  1.000.000
razão:  1.000x

N=10.000 comparações:
O(N):   10.000
O(N²):  100.000.000
ratio:  10.000x

Em N=10, a diferença mal é perceptível. Em N=10.000, o algoritmo O(N²) executa 10.000 vezes mais devagar. É por isso que MOAD-0001 permaneceu invisível por décadas: os grafos em que ele era executado em 1993 tinham 50 nós. Em 2020, o mesmo código era executado em grafos de dependência com 50.000 nós.

Classifique Três Operações

Aplique as classes de complexidade a operações concretas. A pergunta-chave para cada uma: quantas operações são necessárias à medida que N cresce?

Código Correto, Curva de Crescimento Errada

Código correto que executa em tempo O(N²) produz resultados idênticos ao código O(N). Os testes passam. A saída coincide. Nenhuma exceção é disparada. O defeito se esconde na curva de crescimento.

Essa propriedade torna os defeitos O(N²) sedimentares: eles se calcificam dentro de código funcional e só se tornam visíveis quando N cresce além de um limiar. O código não mudou. O mundo ao seu redor mudou.

MOAD-0001: O Defeito Sedimentar

A instância mais comum: visited = [] dentro de um loop de travessia em grafo.

visited = []
for node in graph:
if node not in visited:  # varredura O(N) a cada chamada
visited.append(node)
process(node)

Cada chamada not in visited percorre de 0 até len(visited)-1 itens. N chamadas × média de N/2 itens verificados = O(N²) no total. A correção: uma linha.

visited = set()  # teste de pertinência O(1)
for node in graph:
if node not in visited:  # busca em hash O(1)
visited.add(node)
process(node)

Mesmo comportamento. Mesma saída. Mesmos testes passando. A taxa de crescimento muda de O(N²) para O(N). Em N=1.000: 1.000× mais rápido. Em N=10.000: 10.000× mais rápido.

Por que a Era de Hamming Plantou Isso

No Java e C iniciais, ArrayList (array dinâmico) era o contêiner sequencial padrão. Conjuntos existiam, mas não eram idiomáticos — os desenvolvedores recorriam ao que era familiar. Uma travessia de grafo de 1993 com N=50 executava em microssegundos com visited = []. Esse código entrou no controle de versão, foi copiado, foi encapsulado em bibliotecas, foi distribuído em gerenciadores de pacotes. Em 2020, o mesmo padrão executava em grafos de dependência com 50.000 nós.

O código estava correto em 1993. Tornou-se caro quando o mundo ao seu redor mudou. A era de Hamming plantou essa classe de defeito ao nunca nomear a questão da taxa de crescimento.

Diagnosticar & Corrigir

Aplique o diagnóstico: encontre o padrão O(N²), identifique a correção.

Que Mudanças de Nomenclatura [BLOCK_TYPE SECTION/STEP]

Antes de Big O ter um nome, os programadores percebiam que “isso fica lento”. Eles faziam profiling. Reescreviam o código. Mas não conseguiam ensinar o padrão — só conseguiam apontar casos isolados. Um padrão sem nome não consegue se propagar. [BLOCK_TYPE SECTION/STEP]

Depois que Big O ganhou um nome, um engenheiro sênior podia dizer “isso é O(N²), substitua por um set” e um engenheiro júnior conseguia entender, aplicar e, por sua vez, ensinar o padrão. O nome transformou o padrão em uma unidade de conhecimento transferível. [BLOCK_TYPE SECTION/STEP]

Hamming reconheceu essa dinâmica em outros domínios. Ele descreveu como nomear “spaghetti code” na década de 1960 permitiu que a comunidade reconhecesse, discutisse e, eventualmente, erradicasse uma classe de defeito que todos haviam experimentado, mas ninguém havia nomeado. O mesmo mecanismo se aplica às classes de complexidade. [BLOCK_TYPE SECTION/STEP]

Unhamming adiciona o vocabulário que Hamming omitiu: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Esses nomes permitem que você veja a curva de crescimento no código que lê, preveja o desempenho em escala e comunique correções com precisão. Eles satisfazem o próprio critério de Hamming para um conceito fundamental: durável e gerador da maior parte do restante do campo. [BLOCK_TYPE SECTION/STEP]

Da Teoria dos Números à Ciência da Computação

A notação Big O não surgiu na ciência da computação. Ela surgiu na matemática pura — especificamente na teoria dos números — 74 anos antes de Donald Knuth adaptá-la para algoritmos.

Paul Bachmann, 1894

Paul Bachmann, um matemático alemão, introduziu a notação O em seu livro de 1894 Die Analytische Zahlentheorie (Teoria Analítica dos Números). Ele precisava de uma forma compacta de expressar que uma quantidade cresce não mais rápido que outra, até um fator constante. Escrever 'f(n) = O(g(n))' significava: f cresce no máximo tão rápido quanto g. Isso permitiu que os teóricos dos números raciocinassem sobre termos de erro em aproximações sem precisar acompanhar constantes exatas.

Bachmann não estava pensando em loops, estruturas de dados ou tempo de execução. Ele estava pensando em como os números primos se distribuem — especificamente sobre os termos de erro no Teorema dos Números Primos.

Edmund Landau, 1909

Edmund Landau, outro matemático alemão, popularizou a notação em seu Handbuch der Lehre von der Verteilung der Primzahlen (Manual sobre a Distribuição dos Números Primos) de 1909. Landau também introduziu a notação relacionada o (little-o) e usou a família de símbolos assintóticos de forma tão extensa que a família ficou conhecida como notação de Bachmann-Landau ou simplesmente notação de Landau.

Durante seis décadas, a notação O viveu inteiramente na matemática. Nenhum programador pensava nela.

Donald Knuth, 1968 & 1976

Donald Knuth traduziu a notação para a ciência da computação. Em The Art of Computer Programming (Vol. 1, 1968), Knuth usou a notação O para descrever o tempo de execução de algoritmos — uma transposição direta da ferramenta de Bachmann para um novo domínio. Ele foi o primeiro a aplicá-la sistematicamente à análise de algoritmos.

Em 1976, Knuth publicou um artigo curto na SIGACT News intitulado 'Big Omicron and Big Omega and Big Theta.' Ele introduziu Omega (Ω) para limites inferiores e Theta (Θ) para limites apertados, completando o vocabulário de três símbolos que a ciência da computação usa hoje. Ele também defendeu a padronização do uso desses símbolos em todo o campo — um ato de padronização deliberada que acelerou a adoção.

No início dos anos 1980, Big O aparecia em todos os livros didáticos de algoritmos. Nos anos 1990, tornou-se vocabulário padrão de entrevistas.

Uma jornada de 74 anos

1894 — Bachmann introduz O na teoria dos números
1909 — Landau populariza O, o e toda a família de notações
1953 — Hamming inicia pesquisa nos Bell Labs (nunca aprende Big O como ferramenta de CS)
1968 — Knuth aplica O à análise de algoritmos no TAOCP Vol. 1
1976 — Knuth adiciona Omega e Theta; defende a padronização
1980s — Big O entra em todos os currículos de CS
1993 — Camada de sedimento MOAD-0001 se forma em código de produção
1995 — Hamming ensina a versão final de seu curso; nunca aborda Big O
2026 — MOAD-0001 encontrado em mais de 1.000 projetos open-source

A ferramenta de Bachmann passou 74 anos na matemática pura, visível para todo matemático, mas invisível para todo programador. Knuth viu o transplante. Hamming — trabalhando na mesma época, colaborando com a mesma comunidade de computação — nunca a incluiu em seu curso.

Por que a Padronização de Knuth Importou

O artigo de Knuth de 1976 fez algo além de introduzir Omega e Theta. Ele argumentou que o campo precisava de uma notação consistente e que a notação inconsistente era ativamente prejudicial. Diferentes livros-texto usavam O para significar coisas diferentes — às vezes como um limite superior, às vezes como uma aproximação, às vezes sem especificar se as constantes importavam. Knuth limpou isso.

Este é o padrão de nomeação de padrões de Hamming aplicado à própria notação. Antes de Knuth padronizar os símbolos, os engenheiros não conseguiam comunicar afirmações de complexidade com precisão entre livros-texto, artigos ou equipes. Após a padronização, 'isso roda em O(N log N)' carregava exatamente um significado, independentemente de quem o dissesse.

Knuth também contribuiu com a tradução informal: 'O(f(n)) significa que o tempo de execução é no máximo uma constante vezes f(n), para todos os n suficientemente grandes.' Essa interpretação — limite superior, até um fator constante, para entradas grandes — tornou-se a intuição padrão que todo programador aprende.