EQST

Suponha que uma função F de N em R+ satisfaz a recorrência F(n) = F([n/2]) + 1 para todo n>= 2; Mostre que F está em (Θlg n).

Suponha que uma função F de N em R+ satisfaz a recorrência F(n) = F([n/2]) + 1 para todo n>= 2; Mostre que F está em (Θlg 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.
  • Suponha que uma função F de N em R+ satisfaz a recorrência F(n) = F([n/2]) + 1 para todo n>= 2; Mostre que F está em (Θlg n).

    • Suponha que uma função F de N em R+ satisfaz a recorrência F(n) = F([n/2]) + 1 para todo n>= 2; Mostre que F está em (Θlg n).


    Olá, Júnior. 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 for, além de par, uma potência de 2.Assim:  Verifica-se, portanto, que, em geral:  

    Páginas populares: