Confira o enunciado: Clique aqui Esse algoritmo Insert-Sort executa as instruções, no pior caso, em tempo O(n2), portanto pertence à classe polinom...

Confira o enunciado: Clique aqui
Esse algoritmo Insert-Sort executa as instruções, no pior caso, em tempo O(n2), portanto pertence à classe polinomial. O algoritmo Insert-Sort executa, no seu pior caso, em O(n2), portanto pertence à classe P (polinomial). Os algoritmos que pertencem à classe polinomial são capazes de executar em O(nk); qualquer tempo acima disso torna o algoritmo não polinomial. Apesar de ele pertencer à classe P, o tempo de execução desse algoritmo pode ser melhorado. A pesquisa binária trabalha com divisão e conquista, portanto apresenta tempo de execução nlogn; consequentemente, pode melhorar o tempo de execução do algoritmo Insert Sort. No entanto, os fatores constantes do Insert-Sort o tornam mais rápido para um pequeno valor de entrada (n). Assim, faz sentido usar o algoritmo Insert-Sort quando os subproblemas se tornam suficientemente pequenos. O algoritmo Insert-Sort, comparado com o Merge-Sort, será mais eficiente que este último no melhor caso, pois o Insert-Sort consegue executar nessa situação O(n).
A. Esse algoritmo Insert-Sort executa as instruções, no pior caso, em tempo O(n2), portanto pertence à classe polinomial.
B. Esse algoritmo Insert-Sort pertence à classe P, e uma melhora no tempo de execução desse algoritmo torna-se dispensável.
C. A pesquisa binária não pode melhorar o tempo de execução no pior caso do Insertion-Sort, pois tem tempo de execução Θ(n3).
D. Sabe-se que o método de ordenação Merge-Sort executa, no seu melhor caso, O(nlogn); portanto, esse algoritmo sempre será melhor que o algoritmo Insert-Sort.