GabaritoC — O(log n)
Gabarito: letra C. A pesquisa binária, no pior caso, possui complexidade de tempo O(log n), pois a cada iteração o intervalo de busca é reduzido pela metade, resultando em aproximadamente log₂(n) passos para encontrar o elemento ou concluir que ele não existe.
A banca cobra o conhecimento da notação Big-O para algoritmos clássicos de busca. A pesquisa binária só é aplicável a listas ordenadas e sua eficiência é exponencialmente superior à busca linear (O(n)) para grandes volumes de dados.
Decore as complexidades dos algoritmos mais comuns: busca linear O(n), busca binária O(log n), bubble sort O(n²), merge sort O(n log n). Em provas, a banca costuma testar justamente a diferença entre O(n) e O(log n) — o termo "redução pela metade" é o gatilho para O(log n).
O(1) corresponde a tempo constante, como o acesso direto a um elemento de array por índice. A pesquisa binária não é constante, pois depende do tamanho da lista.
O(n) é a complexidade da busca linear (sequencial). Na pesquisa binária, o número de comparações cresce logaritmicamente, não linearmente.
O(log n) é a complexidade correta. A cada passo, o algoritmo descarta metade dos elementos restantes, o que leva a log₂(n) comparações no pior caso.
O(n log n) é típico de algoritmos de ordenação eficientes (como merge sort ou heapsort). Não se aplica à busca binária.
Gabarito: letra C
Link permanente: /questoes/qg295027