Fibonacci - Dynamic Programming + Optmized versions

f (1) = 1

f (2) = 1

f (3) =  f(1) + f (2)

f (4) =  f(2) + f (3)

f (n) =  f(n-2) + f(n-1)

         f(1)        f(2)

            \         /   |

              f(3)      |

                |    \    |

                |     f(4)

                |     /   |         

                f (5)   |

                  |    \  |

                  |    f(6)

                  |     /

                 f(7)

To solve the fibonacci problem the naive solution is simple as the following

unsigned long fibonacci(int n) {

        if (n < 2)

                return 1;

        return  fibonacci(n-2) + fibonacci(n-1);

}

Using the naive recursive approach we will end up doing the same recursive call more than once, for example to calculate to calculate f(4) and f (3), we calculate f(2) , to calculate f(4) and f(5) we calculate f(3), to calculate f(5) and f(6) we use f(4) and so on.

T(n) = T(n-1) + T(n-2) + c
= 2T(n-1) + c //from the approximation T(n-1) ~ T(n-2)
= 2*(2T(n-2) + c) + c
= 4T(n-2) + 3c
= 8T(n-3) + 7c
= 2^k * T(n - k) + (2^k - 1)*c

Let's find the value of k for which: n - k = 0
k = nT(n) = 2^n * T(0) + (2^n - 1)*c
= 2^n * (1 + c) - c

The complexity time of this algorithm will be  O (2^n)

Using Dynamic programming (recursion + memoization) we can reduce this time, simply saving already calculated results in a dictionary and avoid repetitive recursion calls by just consulting the dictionary.

The Dynamic programming version of fibonacci that runs in O(n) time.

unsigned long fibonacci(int n, unordered_map<unsigned long,unsigned long> &map) {

        if (map.find(n) != map.end()) {

                return map[n];

        }

        if (n < 2)

                return 1;

        map[n] = fibonacci(n-2, map) + fibonacci(n-1, map);

        return map[n];

}

Optimized version saving space

Time: O(n) , Space O(1)

int fib(int n)
{
    int a = 0, b = 1, c, i;
    if( n == 0)
            return a;
    for(i = 2; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
} 

And finally the most optmized version of fibonacci,

Time: O(1) , Space(1)

int fib(int n) {
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n) / sqrt(5));
}