O(log n)

O que significa

O(log n) quer dizer que o trabalho cresce bem devagar em relação ao tamanho da entrada.

Isso costuma acontecer quando cada passo elimina uma fatia grande do problema.

Forma comum

O exemplo clássico é busca binária.

Você não percorre item por item.

Você olha o meio e decide qual metade ainda faz sentido.

Quando importa

O(log n) costuma aparecer quando:

• os dados estão ordenados
• você consegue descartar metade do espaço de busca
• a próxima decisão depende do resultado atual

Pergunta melhor

Em vez de decorar “busca binária é O(log n)”, vale perguntar:

1. eu consigo eliminar metade do problema por passo?
2. os dados permitem isso sem quebrar a lógica?
3. a entrada já está ordenada ou vou pagar esse custo antes?