MO417 - Questão para a prova oral

Número: 

Enunciado: Seja o vetor A=[2^n-1, 2^n-2, ……, 1], se aplicamos o algoritmo counting-sort para ordenar o vetor A, quais das seguintes afirmações são verdadeiras:

  (I)  Si n ≥ lg 2cn, a ordenação funciona em Θ(n), para c=1.

 (II)  Si n ≤ lg 2cn, a ordenação funciona em Θ(n), para c=1.

(III)  O algoritmo counting-sort sempre cumpre a propriedade de estabilidade.

Assinale a alternativa correta:

1. Somente (I) é verdadeira.
2. Somente (II) é verdadeira.
3. (I) e (II) são verdadeiras.
4. (II) e (III) são verdadeiras.
5. NDA

Ideia original de: Jhon Anthony Campos Arteaga