This post is the last of a series of posts in where I discuss different ways of generating Fibonacci sequence. A natural question that arises is then: which of the different implementations are the best?

For sure you can say that the recursive implementation is the worse. This is because it is easy to prove that to compute $f_n$, a number of $O(f_n)$ additions (and therefore also function calls) are needed¹.

From a practical perspective, the recursive algorithm becomes impractical when computing even small instances. The figure below shows execution time that took to run the recursive algorithm to compute ${f_n}$ where $n$ is the Fibonacci index number. I implemented the same algorithm in both C++ and javascript for comparison. Although C++ is the fastest, both algorithms present what it looks like an exponential growth of the execution time as instance size increases².

The complexity of the iterative algorithm (C++, javascript) is only $O(n)$¹ and therefore it is efficient in generating Fibonacci sequence. The closed-form can be seen as evaluating a n-order polynomial and therefore I would also expect a complexity of $O(n)$³.

The highest number I was able to compute with a double float number in C++ was $f_{1476} = 1.3069892237633987e+308$ and it took about 5 ms for both iterative and closed-form algorithms. For javascript, nodejs took about 150 ms for both types of algorithms.

You can argue that the closed-form form is not only efficient but also aesthetically more pleasing. However, there is more than mere beauty in it, because it also allows us to deduce that the Fibonacci series growth exponentially

and therefore, it can be proved that recursive implementation of the Fibonacci sequence has exponential complexity or $O(\varphi^n)$.

References