Questão comentada Policia Federal 2025 Cebraspe – Perito Criminal Federal – Área 3: Informática Forense – Questão 78: Complexidade de algoritmos

Gabarito: B

Errado. Para entradas grandes, O(n) é mais eficiente que O(n log n), e não o contrário. A função n log n é o produto de n por log n; como log n cresce (ainda que devagar) à medida que n aumenta, n log n acaba superando n. Exemplo: com n = 1.000.000, n log₂ n ≈ 20 milhões de operações, contra 1 milhão do algoritmo linear.

Base legal: Fundamento: análise assintótica (n log n = n × log n) e documentação Microsoft, List .Sort Para n > 2, log₂ n > 1, logo n log₂ n > n; com n = 1.000.000, n log₂ n ≈ 19.931.569. List .Sort: "This method is an O(n log n)...