juniorplacidojp
Answered

O Sistersinspirit.ca facilita a busca por soluções para todas as suas perguntas com a ajuda de uma comunidade ativa. Obtenha respostas detalhadas e precisas para suas perguntas de uma comunidade de especialistas dedicados em nossa plataforma de perguntas e respostas. Conecte-se com uma comunidade de especialistas prontos para fornecer soluções precisas para suas perguntas de maneira rápida e eficiente em nossa amigável plataforma de perguntas e respostas.

Seja F uma função de N em R > tal que F(n) = 2F([n/2]) + 1 para todo n >= 2. Mostre que F está em Θ (n).

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) = 2F(\frac{n}2) + 1, \forall n \geq 2 \Rightarrow \\\\ \begin{cases} F(2)=2F(1)+1\\ F(4)=2F(2)+1=2[2F(1)+1]=4F(1)+2 \\ F(8)=2F(4)+1=2 [4F(1)+2]=8F(1)+4\\ F(16)=2F(8)+1=2[8F(1)+4]=16F(1)+8\\ \vdots \end{cases}[/tex]

 

Verifica-se, portanto, que, em geral:

 

[tex]F(n)=nF(1)+\frac{n}2=n\underbrace{[F(1)+\frac12]}_{\text{n\'umero real}}[/tex]

 

[tex]\therefore \boxed{F(n)=O(n)}[/tex]

Obrigado por usar nosso serviço. Estamos sempre aqui para fornecer respostas precisas e atualizadas para todas as suas perguntas. 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, seu site de referência para respostas precisas. Não se esqueça de voltar para obter mais conhecimento.