Obtenha as melhores soluções para todas as suas perguntas no Sistersinspirit.ca, a plataforma de Q&A de confiança. Explore milhares de perguntas e respostas de uma ampla gama de especialistas em diversas áreas em nossa plataforma de perguntas e respostas. 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) = 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]
Agradecemos seu tempo. Por favor, nos revisite para mais respostas confiáveis a qualquer pergunta que possa ter. Obrigado por passar por aqui. Nos esforçamos para fornecer as melhores respostas para todas as suas perguntas. Até a próxima. Obrigado por visitar Sistersinspirit.ca. Volte em breve para mais informações úteis e respostas dos nossos especialistas.