Pergunta das aulas 11/03 e 13/03

MO417 - Questao para a prova oral

Numero:

Enunciado: Dada as seguintes afirmações

I. Se produz um heap máximo a partir de um vetor de tamanho n não ordenado em O(n).

II. A função f(n)=1/(2^n) não satisfaz condição de regularidade do teorema mestre a.f(n/b)<=c.f(n), para um c<1.

III. O tempo de execução de um algoritmo A é descrito pela recorrência T(n) = 7T(n/2) + n²,
um outro algoritmo A' tem um tempo de execução descrito pela recorrência T'(n) = aT'(n/4) + n²
O maior valor inteiro de a para que A' seja assintoticamente mais rápido que A é 49.

assinale a alternativa correta:

a) Apenas a afirmação I é verdadeira.
b) As afirmações I e II são verdadeiras.
c) Apenas a afirmação II é verdadeira.
d) As afirmações II e III são verdadeiras.
e) NDA.

Ideia original de: Lucas Miguel de Carvalho