Notação Big O — Complexidade de Tempo Explicada de Forma Simples

A notação Big O diz quão rápido o tempo de execução ou o uso de memória de um algoritmo pode crescer à medida que o tamanho da entrada aumenta. Se você está perguntando “o que acontece quando o problema fica muito maior?”, Big O é a forma padrão de responder isso.

É por isso que as pessoas dizem que a busca linear é $O(n)$ e a busca binária é $O(\log n)$. O objetivo não é prever milissegundos exatos em uma máquina específica. O objetivo é comparar padrões de crescimento.

O Que Significa Big O

Se um algoritmo leva tempo $T(n)$ em uma entrada de tamanho $n$, então

$$T(n) = O(f(n))$$

significa que, para algumas constantes $C > 0$ e $n_0$,

$$T(n) \le C f(n) \quad \text{for all } n \ge n_0$$

Isso quer dizer que Big O é uma afirmação de limite superior sobre o crescimento para entradas suficientemente grandes.

Em linguagem simples: quando $n$ é grande o bastante, o tempo de execução não cresce mais rápido do que um múltiplo constante de $f(n)$.

Por Que Big O É Útil

Big O oferece uma forma independente da máquina para comparar algoritmos. Um programa pode rodar mais rápido em um notebook do que em outro, mas a tendência de crescimento continua importando.

Essa tendência importa ainda mais quando o tamanho da entrada muda muito. Um algoritmo que funciona bem para $100$ itens pode se tornar impraticável para $10^6$ itens se sua taxa de crescimento for ruim.

Complexidades de Tempo Comuns em Resumo

• $O(1)$: o trabalho permanece limitado à medida que $n$ cresce.
• $O(\log n)$: o trabalho cresce lentamente, muitas vezes quando o tamanho do problema é reduzido repetidamente.
• $O(n)$: o trabalho cresce aproximadamente em proporção ao tamanho da entrada.
• $O(n \log n)$: um pouco mais do que linear, comum em algoritmos de ordenação eficientes.
• $O(n^2)$: o trabalho cresce como o quadrado do tamanho da entrada, muitas vezes por causa de laços aninhados sobre os mesmos dados.

Esses rótulos comparam crescimento, não velocidade exata. Um algoritmo $O(n)$ ainda pode ser mais lento do que um $O(n^2)$ para entradas pequenas se seus fatores constantes forem grandes.

Exemplo Resolvido: Por Que a Busca Linear É $O(n)$

Suponha que você percorra uma lista da esquerda para a direita procurando um valor-alvo. No pior caso, o valor não está na lista ou está no final, então talvez seja necessário verificar cada item uma vez.

Se a lista tem $n$ itens, o número de verificações pode ser no máximo $n$. É por isso que o tempo no pior caso é

$$O(n)$$

A principal ideia é simples: se o tamanho da lista dobra, o número de verificações no pior caso também pode dobrar aproximadamente. Esse é o padrão que Big O está capturando.

O Que Big O Deixa de Fora

Big O ignora intencionalmente fatores constantes e termos de ordem inferior ao comparar o crescimento para entradas grandes.

Por exemplo, se

$$T(n) = 3n + 2$$

então $T(n)$ ainda é $O(n)$. A constante $3$ e o $2$ extra importam para o tempo exato, mas não mudam o principal padrão de crescimento.

Isso não significa que constantes nunca importam na prática. Significa que Big O responde a uma pergunta mais específica: como o custo escala quando $n$ fica grande.

Erros Comuns com Big O

Erro 1: Tratar Big O como tempo de execução exato

$O(n)$ não significa que o tempo de execução é exatamente $n$ passos. Significa que o crescimento é limitado superiormente por um múltiplo constante de $n$ quando $n$ é grande o bastante.

Erro 2: Esquecer a condição de $n$ grande

A definição formal só precisa valer para todo $n \ge n_0$. Big O trata do comportamento assintótico, não de toda entrada minúscula.

Erro 3: Supor que Big O sempre significa tempo típico de execução

Em discussões sobre algoritmos, Big O muitas vezes descreve o tempo no pior caso, mas isso é uma convenção ligada ao contexto. Complexidade média e complexidade no melhor caso são questões diferentes e devem ser indicadas com clareza.

Erro 4: Comparar algoritmos apenas por Big O

Big O é importante, mas uso de memória, custo de implementação e fatores constantes ainda podem importar muito em sistemas reais.

Onde Você Vê a Notação Big O

Big O aparece em ciência da computação, matemática discreta e análise de desempenho. Ela é especialmente útil ao comparar algoritmos de busca, ordenação, travessia de grafos e programação dinâmica.

De forma mais ampla, ela é usada sempre que você se importa com como um processo escala, e não apenas com seu comportamento em um tamanho fixo.

Tente um Exemplo Parecido

Pegue um laço duplo simples que percorre uma grade $n \times n$. Conte quantas vezes a ação interna é executada. Se o trabalho total cresce como $n^2$, você terá um exemplo concreto de por que laços repetidos sobre os mesmos dados frequentemente levam a um comportamento $O(n^2)$.