A eficácia do método de substituição tem dependência intrínseca da proposição de uma boa solução (bom "chute") para a recorrência, e a verificação ...

A eficácia do método de substituição tem dependência intrínseca da proposição de uma boa solução (bom "chute") para a recorrência, e a verificação da solução é feita por indução matemática. Considere a seguinte recorrência: Marque V para verdadeira e F para falsa a respeito de sua resolução: ( ) Se uma solução genérica O(♦) é proposta para a recorrência, então uma desigualdade do tipo ilustrado a seguir deve ser construída para qualquer valor de c. ( ) Se O(log(n)) é uma solução proposta para a recorrência, então um dos passos do método envolve a avaliação da diferença log(n) – log2, e o método conclui com a validação da solução. ( ) Se O(n2) é uma solução proposta para a recorrência, então o passo final do método vai gerar a expressão a seguir, que confirma a validade da solução. ( ) Se O(n) é uma solução proposta para a recorrência, então a aplicação do método inicia com a substituição da recorrência pela expressão cn + 1 e conclui com a validação da solução. Assinale a alternativa que apresenta a sequência correta: A. V – V – V – F. B. F – F – F – V. C. F – V – F – F. D. V – F – F – V. E. V – V – F – F.