Gabarito disponível
De acordo com Szwarcfiter e Markenzon (2010), em uma lista linear cada nó é formado por campos, que armazenam as características distintas dos elementos da lista. Dessa forma, assinale a opção que apresenta corretamente a complexidade da busca sequencial ou linear, no pior caso, utilizando a notação O.
Resolução comentada
A busca sequencial tem complexidade O(n) no pior caso.
No pior caso o elemento está na última posição ou ausente, e é preciso percorrer todos os n nós da lista. Portanto, a complexidade é linear, O(n).
Análise das alternativas
A) O(n log n) é típica de ordenação eficiente. C) O(n²) e D) O(n³) são polinomiais de ordem maior. E) O(2ⁿ) é exponencial. Nenhuma se aplica a uma única varredura linear.
Referência: Szwarcfiter e Markenzon (2010), Estruturas de Dados e seus Algoritmos.
Resolução comentada do VaiConcursos.