In almost any algorithmic course there is a complexity analysis of the recursive implementation of
Fibonacci numbers.
This is a theory which is used to understand how recursive algorithms are analysed.
However, in real life to produce one more rabbit we only need to have two parent rabbits because
this is how most rabbits are born on earth.
This principle is actually used for Fibonacci numbers if we want to have O(n) efficient implementation
which takes O(C) memory instead of classical recursive one.
Here is it:
template<class number>
number fibonacci(number Nth)
{
//sequence starts with 0, 1, 1, 2, 3, 5
if (0 == Nth) return 0;
if (3 > Nth) return 1;
number tmp[2];
tmp[0] = 0;
tmp[1] = 1;
bool pos = false;
while(Nth-=1)
{
tmp[(char) pos] = tmp[0] + tmp[1];
pos=!pos;
}
return tmp[(char) !pos];
}
As I recently heard we should not be fetish about O() notation.
There are cases when O(n^3) is better than O(n) since there are also constants involved and
for some problems and some data sets we can have:
(1/1000)*(n^3) can be smaller than (100 * n)
The same must be applied to all problems.
By the way, the idea of using precalculated values (something like cache) in recursive routines and cycles is called dynamic programming.