Participe do IDNLearner.com e receba respostas detalhadas. Descubra respostas completas para suas perguntas graças à vasta experiência de nossa comunidade de especialistas.
Sagot :
Olá, Júnior.
Olá, Júnior.
Como o domínio de F(n) é o conjunto dos números naturais, então F(n) está definida se e somente se n/2 for natural, o que implica que n deve ser par.
Portanto, não estão definidas F(3), F(5), F(7), etc.
Como F(3), F(5), F(7), ... não estão definidas, então F(6), F(10), F(14) também não estão definidas, pois, pela relação de recorrência, F(6) = 2F(3) + 1, F(10) = 2F(5) + 1, ... e assim por diante.
F(n) está definida, portanto, apenas quando n for, além de par, uma potência de 2.
Assim:
[tex]F(n) = F(\frac{n}2) + 1, \forall n \geq 2 \Rightarrow \\\\ \begin{cases} F(2)=F(1)+1\\ F(4)=F(2)+1=F(1)+1=F(1)+2=F(1)+\log_22\\ F(8)=F(4)+1=F(1)+2+1=F(1)+3=F(1)+\log_28\\ F(16)=F(8)+1=F(1)+4=F(1)+\log_216\\ \vdots \end{cases}[/tex]
Verifica-se, portanto, que, em geral:
[tex]F(n)=F(1)+\log_2n[/tex]
[tex]\therefore F(n)=O(\log_n)[/tex]
Obrigado por ser parte ativa da nossa comunidade. Continue compartilhando suas ideias e respostas. Seu conhecimento é essencial para nosso desenvolvimento coletivo. Suas perguntas merecem respostas precisas. Obrigado por visitar IDNLearner.com e nos vemos novamente em breve para mais informações úteis.