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).
Soluções para a tarefa
Respondido por
0
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:
Perguntas interessantes
Filosofia,
7 meses atrás
Inglês,
7 meses atrás
Contabilidade,
7 meses atrás
Geografia,
1 ano atrás
Física,
1 ano atrás
Matemática,
1 ano atrás
Matemática,
1 ano atrás
Biologia,
1 ano atrás