GabaritoB — O(log2n)
Gabarito: letra B. O tempo de execução da busca binária no pior caso é O(log₂ n), pois a cada iteração o espaço de busca é reduzido à metade. As demais alternativas representam ordens de crescimento superiores ou incorretas.
O(n) corresponde à busca linear (sequencial), onde cada elemento pode ser verificado. A busca binária é exponencialmente mais eficiente, com O(log n).
A busca binária, no pior caso, executa um número de comparações proporcional ao logaritmo do tamanho da entrada na base 2, ou seja, O(log₂ n).
O(n/2) ainda é O(n) na notação Big-O (constantes são desprezadas). Não corresponde à complexidade da busca binária.
O(2ⁿ) é complexidade exponencial, típica de algoritmos de força bruta para problemas NP-completos. Muito superior a O(log n).
O(n³) é complexidade cúbica, também muito maior que logarítmica.
Na notação Big-O, desprezamos constantes e termos de ordem inferior. Grave que busca binária = O(log n) e busca sequencial = O(n).
Gabarito: letra B.
Link permanente: /questoes/fc064075