O(n²)

O que significa

O(n²) significa que a quantidade de trabalho cresce aproximadamente com o quadrado do tamanho da entrada.

Se a entrada dobra, o trabalho pode ficar perto de quatro vezes maior.

Por isso exemplo pequeno parece tranquilo e exemplo grande piora rápido.

Formato comum

O caso mais clássico e um loop dentro do outro comparando cada item com muitos outros.

for (let i = 0; i < items.length; i += 1) {
  for (let j = 0; j < items.length; j += 1) {
    compare(items[i], items[j])
  }
}

Não e o único jeito de chegar em O(n²), mas e o padrão mais fácil de reconhecer.

Quando importa

O(n²) não e automaticamente errado.

Vira problema quando:

• n pode crescer bastante
• a operação interna e cara
• isso roda vezes suficientes para afetar custo ou experiência

Se n e pequeno e fixo, talvez a solução continue aceitavel.

Pergunta melhor

Não pergunte só “isso e O(n²)?”

Pergunte:

1. quanto n pode crescer de verdade?
2. com que frequência isso roda?
3. existe Hash Map, Set, ordenação ou preprocessamento que evite varredura repetida?

Essa conversa costuma ajudar mais do que teatro de complexidade.