MO417 - Questão para a prova oral

Número: 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, isso porque possuem complexidades O(n²) e O(n lg(n)), respectivamente.
III - O Bubble-Sort e o Insertion-Sort possuem complexidade 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

Autor(a): Matheus Silva Mota