A primeira implementação é trivialmente linear e satisfaz \(O(n)\).
Para encontrar a complexidade computacional da segunda implementação, precisamos notar que a complexidade computacional de \(F(n)\) pode ser calculada pelo número de somas efetuadas:
\(n=1\) temos 0 somas
\(n=2\) temos 0 somas
\(n=3\) temos 1 soma
\(n=4\) precisamos calcular \(F(4)=F(3)+F(2)\) e temos 1 soma
\(n=5\) precisamos calcular \(F(5)=F(4)+F(3)\) e temos 2 somas
\(n=6\) precisamos calcular \(F(6)=F(5)+F(4)\) e temos 3 somas
Logo, o número de somas cresce com o termo \(F(n)\) da sequência de Fibonacci e basicamente precisamos descobrir como \(F(n)\) cresce.
A sequência de Fibonacci é um equação em diferenças com coeficientes constantes e é trivial mostrar que sua solução é dada por
\[F(n)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n \in \Theta(\phi^n),\]
onde \(\phi=\frac{1+\sqrt{5}}{2}\).