Usando a notação Big-O para representar o custo computacional, é correto afirmar que o tempo de execução da busca binária nunca é pior que

Gabarito

B

Comentário do professor

A busca binária exige que o vetor esteja ordenado e funciona comparando o elemento do meio e descartando metade do espaço de busca a cada passo — processo típico de divisão e conquista.

Se no início há \(n\) elementos, após uma comparação sobram \(n/2\), depois \(n/4\), e assim por diante. Após \(k\) comparações o espaço restante é \(n/2^k\). A busca termina quando \(n/2^k \le 1\), isto é, quando \(2^k \ge n\).

Tomando logaritmo base 2, obtém-se \(k \ge \log_2 n\). Assim, no pior caso o número de passos cresce proporcionalmente a \(\log_2 n\), logo a complexidade temporal é \(O(\log_2 n)\).