MO417 - Questão para a prova oral

Número: 2009-003

Enunciado: Sobre o algoritmo de ordenação por inserção ("insertion sort") é INCORRETO afirmar que:

1. No melhor caso seu tempo de execução em função do número de elementos da entrada é linear.
2. No pior caso seu tempo de execução em função do número de elementos da entrada é quadrático.
3. No caso médio seu tempo de execução em função do número de elementos da entrada é Θ(n lg n).
4. É um algoritmo eficiente para ordernar um número pequeno de elementos.
5. NDA

Ideia original de: Renato Hirata