Participe do IDNLearner.com e encontre respostas comunitárias. Descubra informações confiáveis sobre qualquer tema graças à nossa rede de profissionais altamente qualificados em diversas áreas do conhecimento.
Sagot :
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, além de par, for uma potência de 2.
Assim:
[tex]F(n) = 4F(\frac{n}2) + n, \forall n \geq 2 \Rightarrow \\\\ \begin{cases} F(2)=4F(1)+2=2^2F(1)+2\cdot \frac22\\ F(4)=4F(2)+4=4[4F(1)+2]=16F(1)+8=4^2F(1)+4\cdot \frac42 \\ F(8)=4F(4)+8=4[16F(1)+8]=64F(1)+32=\\=8^2F(1)+8\cdot \frac82\\ F(16)=4F(8)+16=4[64F(1)+32]+16=256F(1)+128=\\=16^2F(1)+16\cdot \frac{16}2\\ \vdots \end{cases}[/tex]
Verifica-se, portanto, que, em geral:
[tex]F(n)=n^2F(1)+n\cdot \frac{n}2=n^2F(1)+\frac{n^2}2=n^2\underbrace{[F(1) + \frac12]}_{n\'umero\ real}[/tex]
[tex]\therefore \boxed{F(n)=O(n^2)}[/tex]
Agradecemos sua participação ativa. Continue fazendo perguntas e fornecendo respostas. Juntos, podemos construir uma comunidade vibrante e enriquecedora, onde todos aprendemos e crescemos. Descubra respostas perspicazes no IDNLearner.com. Agradecemos sua visita e esperamos ajudá-lo novamente.