O que é Big-O Notation
Esta é a ferramenta que você vai usar em todas as aulas do curso. Sempre que dissermos "essa solução é O(n)", vamos justificar o porquê — e depois desta seção, você vai conseguir justificar sozinho.
Por que não medimos em segundos?
Imagine que você resolveu um problema e seu código levou 2 segundos. Isso é rápido ou lento? Depende: do seu computador, da linguagem, do que mais estava rodando... Segundos não dizem nada sobre o algoritmo — dizem sobre a máquina.
Por isso medimos outra coisa: como o número de passos cresce quando a entrada cresce. Essa é a pergunta que o Big-O responde:
Se eu dobrar o tamanho da entrada, o que acontece com o trabalho?
- Continua igual? O(1) — constante.
- Dobra junto? O(n) — linear.
- Quadruplica? O(n²) — quadrático.
- Aumenta só um pouquinho? O(log n) — logarítmico.
Por que isso importa tanto no LeetCode
Veja o que acontece com o número de passos quando o array tem 1 milhão de elementos (tamanho comum nos limites do LeetCode):
| Complexidade | Passos com n = 1.000.000 | Na prática |
|---|---|---|
| O(log n) | ~20 | instantâneo |
| O(n) | 1 milhão | instantâneo |
| O(n log n) | ~20 milhões | rápido |
| O(n²) | 1 trilhão | ⏰ Time Limit Exceeded |
| O(2ⁿ) | um número com 300 mil dígitos | impossível |
É por isso que tantos problemas têm uma solução "óbvia" de dois loops que funciona mas não passa: ela é O(n²). O padrão certo derruba para O(n) — e aprender esses padrões é exatamente o objetivo deste curso.
Veja a diferença na prática
O código abaixo conta os passos de duas estratégias para o mesmo problema:
verificar se um array tem elementos duplicados. Rode e compare. Depois,
aumente o tamanho e veja a diferença explodir.
Com 200 elementos: ~19.900 passos contra 200. Com 1 milhão: 500 bilhões contra 1 milhão. O algoritmo importa mais que o computador.
As três simplificações do Big-O
O Big-O é deliberadamente "preguiçoso" — ele ignora detalhes que não mudam o formato do crescimento:
- Constantes caem. O(2n) vira O(n). Por quê? Porque dobrar a velocidade do computador também "multiplica por 2", e nem por isso o algoritmo mudou. O que interessa é a forma da curva, não a inclinação exata.
- Termos menores caem. O(n² + n) vira O(n²). Por quê? Com n = 1.000.000, o n² contribui 1 trilhão e o n contribui 1 milhão — 0,0001% do total. O termo dominante engole o resto.
- Pensamos no pior caso. Se o algoritmo pode ser rápido com sorte mas lento sem ela, o Big-O descreve o "sem sorte". É a garantia que você dá: "nunca pior que isso".
As classes que você vai encontrar
Da mais rápida para a mais lenta:
| Classe | Nome | Exemplo típico |
|---|---|---|
| O(1) | constante | acessar nums[i], inserir num hash map |
| O(log n) | logarítmica | busca binária (corta metade a cada passo) |
| O(n) | linear | percorrer o array uma vez |
| O(n log n) | linearítmica | ordenar (sort eficiente) |
| O(n²) | quadrática | comparar todos os pares (dois loops aninhados) |
| O(2ⁿ) | exponencial | testar todos os subconjuntos |
| O(n!) | fatorial | testar todas as ordens possíveis |
Guarde especialmente estas três, que aparecem o tempo todo nas seções do curso: O(n) é "percorri tudo uma vez", O(n²) é "comparei todos os pares", O(log n) é "cortei pela metade a cada passo".
🧠 Quiz de fixação
0/41. Um algoritmo executa exatamente 3n + 50 passos para uma entrada de tamanho n. Qual é o Big-O dele?
2. Você dobrou o tamanho da entrada e o número de passos quadruplicou. Qual é a complexidade provável?
3. Por que uma solução O(n²) costuma falhar no LeetCode quando n chega a 1 milhão?
4. Um algoritmo faz n² + 10n + 1000 passos. Qual é o Big-O?
Resumo
- Big-O mede como o trabalho cresce com a entrada, não tempo em segundos.
- Constantes e termos menores caem; pensamos no pior caso.
- O(n²) com entrada grande = Time Limit Exceeded. Os padrões do curso existem para derrubar O(n²) para O(n) ou O(n log n).
Na próxima aula: as quatro regras práticas para olhar qualquer código e dizer o Big-O dele — com justificativa.