MO417 - Questão para a prova oral

Número: 2010-008

Enunciado:
I - O Insertion-Sort nunca faz mais do que 2n trocas para ordenar um arranjo de n elementos.
II - Para uma entrada A com n elementos, o Merge-Sort sempre será mais rápido que o Insertion-Sort, isto porque possuem complexidades de pior caso O(n²) e O(n lg n), respectivamente.
III - O Bubble-Sort e o Insertion-Sort possuem complexidade de pior caso de mesma ordem.

Considerando as afirmações I, II e III, qual das alternativas abaixo está correta?

1. Apenas a afirmação I está correta
2. Apenas as afirmações I e II estão corretas
3. As afirmações I e III estão corretas
4. Apenas as afirmações II e III estão corretas
5. NDA

Ideia original de: Matheus Silva Mota