A complexidade de algoritmos considera o tempo de execução que um código usa para solucionar um problema. Selecione a alternativa que mostra a notação da menor complexidade entre a

Gabarito

Errado

Comentário do professor

\(O(\log n)\) representa a complexidade logarítmica, em que o número de operações aumenta muito lentamente conforme cresce \(n\). Em termos práticos, se você dobrar o tamanho da entrada, o custo só aumenta por uma unidade no logaritmo.

Essa complexidade surge em algoritmos que resolvem o problema reduzindo repetidamente o espaço de busca — por exemplo, pelo processo de redução pela metade. A cada passo a quantidade de dados a considerar diminui exponencialmente, portanto o número de passos é proporcional a \(\log n\).

No cálculo assintótico, a base do logaritmo é irrelevante; escrevemos simplesmente \(O(\log n)\). Isso torna esse comportamento muito desejável em operações de busca e estruturas balanceadas, porque escala muito bem para entradas grandes.