O Sistersinspirit.ca está aqui para ajudá-lo a encontrar respostas para todas as suas dúvidas com a ajuda de especialistas. Conecte-se com profissionais em nossa plataforma para receber respostas precisas para suas perguntas de maneira rápida e eficiente. Faça suas perguntas e receba respostas detalhadas de profissionais com ampla experiência em diversos campos.
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 visita. Nossa plataforma está sempre aqui para oferecer respostas precisas e confiáveis. Volte a qualquer momento. Obrigado por escolher nossa plataforma. Estamos dedicados a fornecer as melhores respostas para todas as suas perguntas. Visite-nos novamente. Visite o Sistersinspirit.ca para obter novas e confiáveis respostas dos nossos especialistas.