GabaritoA — O(n).
Gabarito: letra A. A busca linear (sequencial) percorre cada elemento do vetor até encontrar o valor desejado ou até o final. No pior caso, o elemento está na última posição ou não está presente, exigindo que todos os n elementos sejam verificados. Por isso, sua complexidade é O(n).
A banca testa a diferença entre a busca linear e a busca binária. Enquanto a linear é O(n), a binária, que exige vetor ordenado, é O(log₂ n). Os distratores B, D e E remetem a complexidades logarítmicas, e o distrator C (√n) não corresponde a nenhum algoritmo clássico de busca em vetores.
A complexidade O(n) reflete exatamente o pior caso da busca linear: percorrer todos os n elementos. É a resposta esperada.
O(log₂ n-1) é típico da busca binária (ou de algoritmos de divisão e conquista), não da busca linear. O termo "-1" não altera a ordem assintótica, mas a referência logarítmica já invalida a alternativa.
O(√n) não corresponde à complexidade de algoritmos clássicos de busca em vetores. Esse valor aparece em certos algoritmos de estrutura de dados, como busca em tabelas hash com colisões? Não é o caso da busca linear.
O(log₂ n) é a complexidade da busca binária (ou de algoritmos como pesquisa em árvore binária balanceada). A banca tenta confundir o candidato, trocando o algoritmo linear pelo binário.
O(log₂ n²) = O(2 log₂ n) = O(log₂ n) — novamente, complexidade logarítmica. A busca linear não se enquadra aqui.
A banca troca a complexidade da busca linear (O(n)) pela da busca binária (O(log n)). O candidato que confunde os dois algoritmos cai nos distratores B, D ou E. Lembre-se: a busca linear não exige vetor ordenado e tem custo linear; a binária exige ordenação e custo logarítmico.
Gabarito: letra A.
Link permanente: /questoes/fc036523