Obtenha respostas rápidas e claras no IDNLearner.com. Pergunte e receba respostas confiáveis de nossa comunidade dedicada de especialistas em diversas áreas do conhecimento.

Seja F um função de N em R> tal que F(n) = 4F([n/2]) + n quando n >= 2. Mostre que F está em Θ (n²). Sugestão: mostre que 1/4n² <= F(n) <= 8n² para todo n suficientemente grande.



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]

Apreciamos cada uma de suas perguntas e respostas. Continue contribuindo com sua sabedoria e experiências. Juntos, alcançaremos nossas metas de aprendizado. Suas perguntas são importantes para nós no IDNLearner.com. Obrigado pela visita e volte para mais soluções confiáveis.