Questão de Algoritmos

Soluções fechadas para recursões podem ser validadas pelo método da substituição. Esse método depende da identificação de constantes positivas, que possam ser usadas para delimitar a função cujo comportamento está sendo analisado. Nesse cenário, analise as asserções a seguir e a relação proposta entre elas.


I. A recorrência T(n) = 2T(n/2) + n é limitada superiormente por O(n ext{log}(n)).


Porque:


II. É possível definir uma constante positiva c, que torna verdadeira a desigualdade 2c(n/2) ext{log}(n/2) + n leq cn ext{log}(n/2) + n.

A
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
B
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
C
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
D
As asserções I e II são proposições falsas.
E
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.

Ainda não há comentários para esta questão.

Seja o primeiro a comentar!

Aulas em vídeo Em breve

00:00

Tópicos Relacionados