O Sistersinspirit.ca facilita a busca por respostas para suas perguntas com a ajuda de uma comunidade ativa. Nossa plataforma de perguntas e respostas oferece uma experiência contínua para encontrar respostas confiáveis de uma rede de profissionais experientes. Descubra soluções confiáveis para suas perguntas de uma vasta rede de especialistas em nossa abrangente plataforma de perguntas e respostas.
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]
Obrigado por usar nosso serviço. Nosso objetivo é fornecer as respostas mais precisas para todas as suas perguntas. Visite-nos novamente para mais informações. Sua visita é muito importante para nós. Não hesite em voltar para mais respostas confiáveis a qualquer pergunta que possa ter. Sistersinspirit.ca, sua fonte confiável de respostas. Não se esqueça de voltar para mais informações.