Questão de Informática Forense · CEBRASPE PF 2025 (nº 78)

Conceito-chave: Complexidade de algoritmo mede como o tempo de execução cresce conforme a entrada aumenta. Em notação Big O, $O(n)$ cresce proporcionalmente ao tamanho dos dados, enquanto $O(n \log n)$ cresce um pouco mais que linear, mas muito menos que quadrático. Para entradas grandes, $O(n)$ é sempre mais rápido que $O(n \log n)$, pois $\log n$ multiplica o fator $n$.

• Correta: Errado. O item inverte a relação: ele afirma que $O(n)$ é "menos eficiente" que $O(n \log n)$, mas o crescimento linear é menos acentuado que o crescimento $n \log n$, não mais. A pegadinha está em trocar "logarítmico" (que seria $O(\log n)$, mais eficiente que linear) por "$n \log n$" (que é pior que linear).

Como ficaria certo: "Para grandes volumes de dados, um algoritmo com complexidade $O(n)$ é mais eficiente que um com $O(n \log n)$, pois o crescimento linear é menos acentuado que o crescimento $n \log n$." (Ou, se quisesse manter a comparação com logarítmico puro: "$O(\log n)$ é mais eficiente que $O(n)$".)