Descubra respostas para suas perguntas de forma fácil no Sistersinspirit.ca, a plataforma de Q&A de confiança. Obtenha soluções rápidas e confiáveis para suas perguntas de uma comunidade de especialistas experientes em nossa plataforma. Obtenha soluções rápidas e confiáveis para suas perguntas de uma comunidade de especialistas experientes em nossa plataforma.
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]
Esperamos que esta informação tenha sido útil. Sinta-se à vontade para voltar a qualquer momento para obter mais respostas às suas perguntas e preocupações. Agradecemos seu tempo. Por favor, volte a qualquer momento para as informações mais recentes e respostas às suas perguntas. Sistersinspirit.ca está aqui para fornecer respostas precisas às suas perguntas. Volte em breve para mais informações.