Linear time sorting

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Supondo que, utilizamos o Radix-Sort para ordenar n-números inteiros, com o tamanho máximo de b-bits. Avalie as seguintes afirmações, sabendo que esse algoritmo ordena os números no tempo de Θ((b/r)(n+2^r)) para qualquer valor inteiro positivo r ≤ b:

I - Podemos ordenar esses n-números inteiros no tempo de O(n), estando eles no intervalo de 0 a nⁿ-1.
II - Podemos ordenar esses n-números inteiros no tempo de O(n), estando eles no intervalo de 0 a n³-1.
III - Para chegar a esse limite assintótico é necessário ordenar os d-digitos através de um método estável, como o Merge-Sort.

a. Apenas I está correta.
b. Apenas II está correta.
c. I e II estão corretas.
d. I, II e III estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller