Fib

Vamos inicialmente ver a condição inicial dessa recursão

$$\begin{eqnarray*} T\left( 0\right) & = & 1\\ T\left( 1\right) & = & 1 \end{eqnarray*}$$

Para qualquer, a expressão de tempo desse algoritmo fica

$$T\left( n\right) =T\left( n-1\right) +T\left( n-2\right)$$

Ora, a expressão acima é a função de recorrência que devolve o -ésimo numero de Fibonacci. Logo, a complexidade de tempo desse algoritmo será, para uma entrada , o valor do -ésimo número de Fibonacci, cujo valor é dado pela fórmula:

$$F_{n}=\frac{1}{\sqrt{5}}\left( \phi ^{n}-\hat{\phi }^{n}\right)$$

Ou, arredondando para o inteiro mais próximo:

$$\begin{eqnarray*} F_{n} & = & \left\lfloor \frac{\phi ^{n}}{\sqrt{5}}+\frac{1}{2}\right\rfloor \\ & = & \frac{\phi ^{n}}{\sqrt{5}} \end{eqnarray*}$$

Onde

A demonstração completa da obtenção de pode ser obtida em[3, p.212-219]

Finalmente, para fechar esse item, seria bom resaltar que