Alternativa correta: C - o algoritmo B tende a ser mais eficiente que o algoritmo A para grandes valores de n.

1. Tema central da questão

O tema da questão é complexidade assintótica de algoritmos, tópico fundamental em estrutura de dados e algoritmos. O desempenho de um algoritmo é medido, principalmente, pelo crescimento do tempo de execução conforme o tamanho da entrada (n) aumenta. A notação O (Big O) representa o quanto o tempo de execução cresce nos piores casos.

2. Resumo teórico

O(n²) indica que o tempo de execução cresce proporcionalmente ao quadrado do tamanho da entrada. Já O(n log n) cresce mais lentamente, pois a função logarítmica aumenta muito devagar em comparação com n.

Para valores grandes de n, O(n log n) será sempre menor que O(n²). Por isso, algoritmos com O(n log n) são preferidos para grandes volumes de dados, como nos algoritmos de ordenação Merge Sort e Quick Sort (citado em Cormen et al., Algoritmos: Teoria e Prática).

3. Justificativa da alternativa correta

C está correta porque, à medida que o tamanho da entrada aumenta, o termo n² cresce muito mais rápido do que n log n, tornando o algoritmo B significativamente mais eficiente para grandes valores de n.

4. Análise das alternativas incorretas

A está errada: resolver o mesmo problema não significa ter o mesmo desempenho.

B está errada: O algoritmo A (O(n²)) quase sempre será menos eficiente para grandes n.

D está errada: O(n²) não tem melhor escalabilidade que O(n log n). Escalabilidade é justamente a capacidade de lidar bem com grandes volumes de dados.

E está errada: O algoritmo B (O(n log n)) é, em geral, mais eficiente para grandes entradas.

5. Estratégias de interpretação

Fique atento quando a questão mencionar "grandes valores de n". Compare o crescimento das funções envolvidas. Desconfie de termos absolutos como "sempre" ou "em qualquer situação" sem considerar a complexidade.

Gostou do comentário? Deixe sua avaliação aqui embaixo!

O algoritmo A tem complexidade O(n²) — seu tempo de execução cresce proporcionalmente ao quadrado do tamanho da entrada.

O algoritmo B tem complexidade O(n log n) — seu tempo cresce mais lentamente, quase linear, multiplicado por um fator logarítmico.

Avaliando as alternativas:

• A) Errado — resolver o mesmo problema não garante desempenho idêntico.
• B) Errado — para grandes entradas, O(n log n) é geralmente mais eficiente que O(n²).
• C) Correto — para valores grandes de n, o algoritmo B tende a ser mais eficiente.
• D) Errado — O(n log n) tem melhor escalabilidade que O(n²).
• E) Errado — o algoritmo B é mais eficiente para entradas grandes.