Última atualização: 2026-06-23

Taxa de crescimento Big-O

A notação Big-O classifica como a demanda de recursos de um algoritmo escala com o tamanho da entrada. Em vez de medir segundos em uma máquina específica, ela captura o formato do crescimento — quando n dobra, o trabalho dobra ou quadruplica? As seis complexidades a seguir são as mais frequentes em livros didáticos e entrevistas técnicas.

As seis classes comuns

O(log n) — Logarítmica. Cada passo elimina uma fração constante do trabalho restante. A busca binária em um vetor ordenado de um bilhão de elementos realiza apenas 30 comparações, pois reduz o espaço de busca à metade a cada passo. Consultas em árvores binárias de busca balanceadas e muitas recorrências de divisão e conquista se enquadram nessa classe.

O(n) — Linear. O trabalho cresce em proporção direta ao tamanho da entrada. Percorrer um vetor uma única vez para encontrar o máximo, contar caracteres em uma string ou ler cada elemento de uma lista são todos lineares. Algoritmos lineares são geralmente considerados eficientes.

O(n log n) — Linearítmica. A complexidade mais comum para ordenação. Merge sort, heapsort e Timsort (usado em Python e Java) atingem O(n log n), que também é o limite teórico inferior para ordenação baseada em comparações. Com $n = 10^6$, isso representa cerca de vinte milhões de operações — rápido na prática.

O(n²) — Quadrática. Dois laços aninhados sobre a entrada. Bubble sort, insertion sort e a multiplicação de matrizes ingênua têm complexidade de pior caso O(n²). Com $n = 10^4$, isso equivale a cem milhões de operações; com $n = 10^6$, chega a um trilhão — impraticável para dados de grande volume.

O(2ⁿ) — Exponencial. O trabalho dobra a cada elemento adicional. O algoritmo recursivo ingênuo de Fibonacci recalcula subproblemas de forma exponencial; a enumeração de todos os subconjuntos de um conjunto também cresce como $2^n$. Com n = 40, a contagem ultrapassa um trilhão.

O(n!) — Fatorial. A classe de crescimento mais rápido na análise algorítmica cotidiana. Soluções por força bruta para problemas de permutação — como listar todos os percursos possíveis no Problema do Caixeiro Viajante — realizam uma operação por permutação, e existem $n!$ permutações no total. Com n = 20, a contagem ultrapassa dois quintilhões de operações.

Exemplo com n = 20

$\log_2 20 \approx 4{,}32 \quad\quad 20 \quad\quad 20 \log_2 20 \approx 86{,}4$

$20^2 = 400 \quad\quad 2^{20} = 1\,048\,576 \quad\quad 20! \approx 2{,}43 \times 10^{18}$

A razão entre O(n log n) e O(n!) com n = 20 é de cerca de $10^{16}$ — a diferença entre uma ordenação rápida e um tempo de espera maior do que a idade do universo.

Orientações práticas

Constantes e efeitos de cache dominam para n pequeno; a complexidade domina para n grande. Um limiar em torno de n = 10.000 é onde O(n²) começa a se tornar problemático no hardware moderno (assumindo operações simples). Acima de $n = 10^6$, geralmente é necessário um algoritmo O(n log n) ou melhor. Algoritmos exponenciais e fatoriais exigem aproximações, programação dinâmica ou estratégias de poda para qualquer entrada do mundo real.

Conversor de Base Numérica é útil ao trabalhar com representações binárias do espaço de entrada.