MO417 - Questão para a prova oral

Número:

Enunciado:

Dado o seguinte algoritmo do Bucket Sort:

1 let B[0..n-1] be new array
2 n = length [A]
3 For i = 0 to n-1
4     make B[i] an empty list
5 For i = 1 to n
6     Insert A[i] into list B[floor(nA[i])]
7 For i = 0 to n-1
8     Sort list B[i] with Insertion sort
9 Concatenate the lists B[0], B[1], . . B[n-1] together in order.

Se mudamos a linha 8 e fazemos a ordenação com quicksort quais serão os tempos de execução no caso médio e no pior caso respectivamente:

a) Θ(n) e O(nlgn)
b) Θ(n) e O(n²)
c) Θ(n lg n) e O(n lg n)
d) Θ(n lg n) e O(n²)
e) NDA




Ideia original de: John Edgar Vargas Muñoz