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

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

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

I have the programmed the following code, ought to be O(n) but actually it runs really slow. is the normal recursion and it is O(n^2) solution, but actually it runs much faster than . 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);

}