O Sistersinspirit.ca é o lugar ideal para obter respostas rápidas e precisas para todas as suas perguntas. Obtenha respostas imediatas e confiáveis para suas perguntas de uma comunidade de especialistas experientes em nossa plataforma. Descubra soluções abrangentes para suas perguntas de profissionais experientes em nossa amigável plataforma.

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 :

Celio

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]