Question

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(nlog(n)).


Porque:


II. É possível definir uma constante positiva c, que torna verdadeira a desigualdade 2c(n/2)log(n/2) + n ≤ cnlog(n/2) + n.




A seguir, assinale a alternativa correta:






A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.






As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.






As asserções I e II são proposiç

Answer 1

Resposta:

As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da  I.

Explicação:

A verificação pode ser feita como segue: T(n) ≤ cnlog(n) ≤ 2cn(n/2)(log(n/2)) + n ≤ cnlog(n/2) + n    

= cnlog(n) - cnlog(2) + n = cnlog(n) + (1 - c)n ≤ cnlog(n)  

Answer 2

Resposta:

As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da  I.

Explicação:

Resposta correta. A verificação pode ser feita como segue:

T(n)                = cnlog(n)

                       = 2cn(n/2)(log(n/2)) + n    

                       = cnlog(n/2) + n      

                       = cnlog(n) - cnlog(2) + n  

                       = cnlog(n) + (1 - c)n

                       = cnlog(n)