Complexidade de Algoritmos de Ordenação
Gabarito: letra A. Dentre as opções, O(n) — complexidade linear — é a que apresenta o melhor fator de complexidade, pois o tempo de execução cresce proporcionalmente ao tamanho da entrada, sendo inferior a O(n²), O(2n) (equivalente a O(n) mas com constante maior) e O(n³). Em algoritmos de ordenação, a complexidade ideal para o caso geral é O(n log n), mas O(n) é ainda superior e, entre as alternativas dadas, é a mais eficiente.
Alternativa A — ✅ Correta ⟵ GABARITO
A notação O(n) representa complexidade linear. Um algoritmo com essa complexidade executa em tempo proporcional ao número de elementos – por exemplo, percorrer um vetor uma única vez. É a melhor opção apresentada.
Alternativa B — ❌ Incorreta
O(n²) é complexidade quadrática (ex.: bubble sort, insertion sort no pior caso). O tempo cresce com o quadrado da entrada, tornando-se inviável para grandes volumes de dados.
Alternativa C — ❌ Incorreta
O(2n) é, na verdade, O(n) na análise assintótica (constantes são desprezadas). Apesar de ainda ser linear, a notação padrão para essa classe é O(n). A banca considera O(n) como a melhor representação, pois O(2n) não é usual e pode indicar um algoritmo ligeiramente pior devido à constante, embora ambas pertençam à mesma família linear.
Alternativa D — ❌ Incorreta
O(n³) é complexidade cúbica, ainda pior que a quadrática. Algoritmos com essa complexidade são ineficientes para entradas grandes e raramente utilizados na prática.
Gabarito: letra A