O(n)

O que significa

O(n) quer dizer que o trabalho cresce junto com o tamanho da entrada.

Se a entrada dobra, o trabalho tende a dobrar também.

Forma comum

O caso mais clássico é uma passada simples:

for (const item of items) {
  process(item)
}

Você olha cada elemento uma vez.

Quando importa

O(n) costuma ser um bom sinal em problema de array, string e lista.

Nem sempre é o melhor possível.

Mas quase sempre já é bem melhor do que repetir varredura desnecessária.

Pergunta melhor

Em vez de só perguntar “isso é O(n)?”, vale perguntar:

1. quantas passadas eu estou fazendo?
2. estou repetindo trabalho à toa?
3. existe memória extra que reduziria custo?