MO417 - Questão para a prova oral

Numero:

Dado as seguintes recorrências:
T(n)=   3T(n/3) + n+1
T'(n)=  2T(n/2) + n-1
T''(n)= 4T(n/4 +1) + n/2

E supondo os algoritmos A e B do HeapSort. Sendo A o algoritmo usual e B uma alteração onde cada pai tem 3 filhos, nas subárvores  esquerda, abaixo, direita. Sabendo que tal algoritmo realiza uma comparação a mais no HeapIfy. Podemos afirmar que:

a. O custo de B é superior ao de A mesmo que coincidam com a mesma assintota.
b. B pode ser melhor descrito como a recorrência T(n)
c. Apenas T'(n) e T''(n) são limitadas assintoticamente por Θ(nlogn)
d. A alteração em B não resulta em nenhuma otimização, mesmo para um n suficientemente grande
e. N.D.A

Ideia original de: Otávio Augusto Araújo Silva