EQST

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).

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). Essa é a pergunta que vamos responder e mostrar uma maneira simples de se lembrar dessa informação. Portanto, é essencial você conferir a matéria completamente.

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).


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:  Verifica-se, portanto, que, em geral: