Um dos métodos amplamente utilizados para a solução de recorrências é conhecido como o método da substituição. Sua aplicação é baseada na proposiçã...

Um dos métodos amplamente utilizados para a solução de recorrências é conhecido como o método da substituição. Sua aplicação é baseada na proposição de uma solução fechada para a recorrência, seguida de uma validação dessa solução. Considerando o uso desse método para verificar se O(n2) é solução para a recorrência T(n) = T(n - 1) + n, analise as afirmativas a seguir. I. Após a construção da desigualdade inicial, o próximo passo envolve a avaliação de n na solução proposta. II. Um dos passos da resolução envolve a avaliação de uma diferença, elevada à potência de 2, entre dois termos. III. A aplicação do método se inicia com a construção da desigualdade T(n) ≤ c(n2 - n), onde c > 0. IV. A conclusão da aplicação do método é que a solução proposta resolve a recorrência em questão. Está correto apenas o que se afirma em: II e IV. Resposta correta. A aplicação do método implica nos seguintes passos: T(n) = T(n – 1) + n = c(n – 1)2 + n = cn2 – 2cn + c + n = cn2 – n(2c – 1) + c = O(n2) Logo, O(n2) é solução para a recorrência.

I. Após a construção da desigualdade inicial, o próximo passo envolve a avaliação de n na solução proposta.
II. Um dos passos da resolução envolve a avaliação de uma diferença, elevada à potência de 2, entre dois termos.
III. A aplicação do método se inicia com a construção da desigualdade T(n) ≤ c(n2 - n), onde c > 0.
IV. A conclusão da aplicação do método é que a solução proposta resolve a recorrência em questão.
a) I e II.
b) II e III.
c) II e IV.
d) III e IV.