Question

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

Answer 1

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:

 

$<var>F(n) = F(\frac{n}2) + 1, \forall n \geq 2 \Rightarrow \\\\ \begin{cases} F(2)=F(1)+1\\ F(4)=F(2)+1=F(1)+1=F(1)+2=F(1)+\log_22\\ F(8)=F(4)+1=F(1)+2+1=F(1)+3=F(1)+\log_28\\ F(16)=F(8)+1=F(1)+4=F(1)+\log_216\\ \vdots \end{cases}</var>$

 

Verifica-se, portanto, que, em geral:

 

$<var>F(n)=F(1)+\log_2n</var>$

 

$<var>\therefore F(n)=O(\log_n)</var>$