Questão de Tecnologia da Informação · FGV PCAM 2021 (nº 46)

A complexidade de algoritmos descreve como o tempo de execução (ou uso de memória) de um algoritmo cresce à medida que o tamanho da entrada, N, aumenta, usando a notação Big O. A busca binária é um algoritmo que encontra um item em uma lista ordenada dividindo repetidamente a parte da lista onde o item pode estar pela metade.

(A) Correta: A busca binária reduz o espaço de busca pela metade a cada passo. Isso significa que o número de operações é proporcional ao logaritmo de N (base 2), pois $2^k = N$ implica $k = \log_2 N$.
(B) Incorreta: Esta complexidade é comum em algoritmos de ordenação eficientes, como Merge Sort ou Quick Sort, que dividem a lista e depois combinam os resultados.
(C) Incorreta: Esta é a complexidade da busca linear, onde no pior caso, o algoritmo precisa verificar cada um dos N elementos da lista. A armadilha aqui é confundir a busca binária (que exige lista ordenada e divide o espaço) com a busca linear (que percorre elemento por elemento).
(D) Incorreta: Embora $N/2$ seja um número de operações, em notação Big O, constantes são ignoradas, então $O(N/2)$ é equivalente a $O(N)$. Não representa a natureza logarítmica da busca binária.
(E) Incorreta: Esta complexidade é típica de algoritmos com laços aninhados que iteram sobre todos os elementos, como alguns algoritmos de ordenação ineficientes (ex: Bubble Sort).