GabaritoA — O (n)
Gabarito: letra A. A busca sequencial (ou linear) percorre cada elemento do vetor até encontrar o alvo ou esgotar a lista. No pior caso – quando o elemento está na última posição ou não está presente – são realizadas n comparações, resultando em complexidade O(n). Esse é um conceito fundamental de análise de algoritmos: a busca linear tem tempo linear, enquanto a busca binária, que exige vetor ordenado, tem tempo O(log n).
A banca testa o conhecimento básico de notação Big-O, que desconsidera constantes multiplicativas e termos de menor ordem. Assim, O(n) é a resposta correta; as demais alternativas representam confusões com a busca binária ou com a eliminação indevida de constantes.
A busca sequencial, no pior caso, examina todos os n elementos. O tempo de execução cresce proporcionalmente ao tamanho da entrada, caracterizando complexidade linear O(n). O contexto de apoio (C1) confirma: "Busca linear cuja ordem é O(n)".
O(log₂n) é a complexidade da busca binária, que exige vetor ordenado e divide o espaço de busca pela metade a cada iteração. Não se aplica à busca sequencial.
O(n/2) sugere que, no pior caso, a busca percorre metade dos elementos, o que é falso: no pior caso, percorre todos os n elementos. Além disso, a notação Big-O ignora constantes, então O(n/2) é equivalente a O(n), mas a expressão O(n/2) não é a forma padrão e não corresponde ao comportamento real da busca linear.
O(2n) também é O(n) (constantes são descartadas), mas a busca sequencial não realiza 2n comparações; realiza exatamente n comparações no pior caso. A alternativa tenta confundir com uma interpretação incorreta da notação.
O(log₂n²) simplifica para O(2 log n) = O(log n), que é novamente a complexidade da busca binária. Não se aplica à busca sequencial.
A banca troca a complexidade da busca linear (O(n)) pela da busca binária (O(log n)) nas alternativas B e E. O candidato desatento pode confundir os dois algoritmos. Lembre-se: sequencial = linear; binária = logarítmica.
Gabarito: letra A
Link permanente: /questoes/fc064199