O algoritmo a seguir é usado para ordenar dados de um vetor.   INSERT-SORT(A) 1 for ⟵ 2 to length[A] 2                   do key ⟵ A[j] 3          ...

O algoritmo a seguir é usado para ordenar dados de um vetor.

INSERT-SORT(A)

1 for ⟵ 2 to length[A]

2                   do key ⟵ A[j]

3                                           ⊳Insert A[j] into the sorted sequence A[1..j – 1].

4                                           i ⟵ j – 1

5                                           while i > 0 and A[i] > key

6                                 do A[i+1] ⟵ A[i]

7                                             i ⟵ i – 1

8                     A[i+1] ⟵ key

Observe que o laço While das linhas 5-7 usa uma busca linear percorrendo de trás para a frente o vetor ordenado A[1...j-1]. Em relação a esse algoritmo, marque a alternativa correta:

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.

E. Esse algoritmo ordenação por inserção executa as instruções no pior caso em tempo O(2n ), portanto pertence à classe polinomial.