Usando a notação Big-O, a complexidade da busca sequencial ou linear é, no pior caso,

Gabarito

A

Comentário do professor

A alternativa correta é O(n). Na busca linear, percorremos os elementos um a um até encontrar o alvo ou acabar a estrutura; no pior caso é preciso inspecionar todos os \(n\) elementos.

Como o número de operações cresce proporcionalmente ao número de elementos, o tempo de execução aumenta de forma linear. Se duplicarmos \(n\), aproximadamente duplicam-se as verificações necessárias.

Por isso a complexidade assintótica no pior cenário é \(O(n)\): o custo é limitado por uma função linear de \(n\), que domina constantes e termos de menor ordem.