Why my dynamical programming of fibonacci doesn't give a linear time?

Question

I am watching this video. Basically it says that using a

dictionary

(python's language?) will make calculate fibonacci from time O(n^2) to O(n).

I have the programmed the following code,

fibo1

ought to be O(n) but actually it runs really slow.

fibo2

is the normal recursion and it is O(n^2) solution, but actually it runs much faster than

fibo1

. How can I understand this?

#include <iostream>

#include <map>

int fibo1(int i, std::map<int,int>& m);

int fibo2(int i);



int main()

{

    std::map<int,int> m;

    m[1] = 1; m[2] = 1;

    int n = 40;

    std::cout << fibo1(n,m);

    //std::cout << fibo2(n);

    return 0;

}



int fibo1(int i, std::map<int,int>& m)   {

    if(m[i]==0)   {

        return fibo1(i-1,m)+fibo1(i-2,m);

    }

    return m[i];

}



int fibo2(int i) {

    if(i==1 || i==2) {

        return 1;

    }



    return fibo2(i-1)+fibo2(i-2);

}

Answer 1

You never actually write the fib[n] at m[n], so you never look up anything and always recalculate it. Use m[i] = fibo1(i-1,m) + fibo1(i-2,m); in the if statement rather than the return line.

Why my dynamical programming of fibonacci doesn't give a linear time?

Sign up