Questão de Tecnologia da Informação · FCC TRT14 2022 (nº 25)

A notação Big-O descreve como o tempo de execução (ou o uso de memória) de um algoritmo cresce à medida que o tamanho da entrada (representado por 'n') aumenta, focando no pior caso. A busca binária é um algoritmo eficiente para encontrar um item em uma lista ordenada, dividindo repetidamente a lista ao meio.

(A) Incorreta: O(n) representa um tempo de execução linear, onde o tempo cresce proporcionalmente ao tamanho da entrada. A busca binária é muito mais eficiente que isso.
(B) Correta: O(log2n) representa um tempo de execução logarítmico. Na busca binária, a cada passo, o espaço de busca é reduzido pela metade, o que leva a um número de operações proporcional ao logaritmo de base 2 do tamanho da entrada (log2n).
(C) Incorreta: O(n/2) ainda é considerado O(n) na notação Big-O, pois constantes multiplicativas (como 1/2) são ignoradas. É uma armadilha para quem pensa que "dividir por 2" na busca binária significa O(n/2), quando na verdade a redução constante do espaço de busca leva a uma complexidade logarítmica, não linear.
(D) Incorreta: O(2ⁿ) representa um tempo de execução exponencial, que é extremamente lento e impraticável para a maioria dos problemas com entradas grandes. A busca binária é muito mais rápida.
(E) Incorreta: O(n³) representa um tempo de execução polinomial cúbico, que também é muito lento para entradas grandes. A busca binária é significativamente mais eficiente.