Buscar

Se a recorrência a ser resolvida satisfaz às condições para a aplicação do teorema mestre, a solução pode ser obtida de forma direta por meio do us...

Se a recorrência a ser resolvida satisfaz às condições para a aplicação do teorema mestre, a solução pode ser obtida de forma direta por meio do uso de um de seus três casos. Para a recorrência a seguir ilustrada, assinale a alternativa correta a respeito do uso do teorema mestre em sua resolução. T(n) = 4T(n/2) + 3
Resposta incorreta.
A. A comparação entre f(n) e nlogbaleva à conclusão de que f(n) < nlogba. Logo, o primeiro caso do teorema pode ser aplicado.
B. A verificação da condição ???????? ( ???? ???? ) ≤ ????????(????) demonstra que a desigualdade não pode ser satisfeita; logo, o terceiro caso do teorema não pode ser usado.
C. Uma constante £ = -1 pode ser utilizada para tornar a igualdade nlogba+£ verdadeira, o que possibilita o uso do segundo caso do teorema.
D. ???? ( ???? ) = ???? ( ????2 ) + ???? , ???????? ???? ≥ 1 ???? ( ???? ) = 1 , ???????? ???? = 0
E. O uso do teorema leva à aplicação do seu terceiro caso, o que implica T(n) apresentar um comportamento assintótico de n3.

Essa pergunta também está no material:

TODAS AS ATIVIDADES
87 pág.

Análise de Algoritmos Faculdade Maurício de Nassau de ParnaíbaFaculdade Maurício de Nassau de Parnaíba

Respostas

8 pessoas visualizaram e tiraram suas dúvidas aqui
User badge image

Ed Verified user icon

A alternativa correta para a resolução da recorrência T(n) = 4T(n/2) + 3 utilizando o Teorema Mestre é a letra A. A comparação entre f(n) e nlogb(a) leva à conclusão de que f(n) < nlogb(a). Logo, o primeiro caso do teorema pode ser aplicado.

0
Dislike0

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

Responda

SetasNegritoItálicoSublinhadoTachadoCitaçãoCódigoLista numeradaLista com marcadoresSubscritoSobrescritoDiminuir recuoAumentar recuoCor da fonteCor de fundoAlinhamentoLimparInserir linkImagemFórmula

Para escrever sua resposta aqui, entre ou crie uma conta

User badge image

Mais conteúdos dessa disciplina