The running time of my code in big O time

Question

So I am doing some practice problems both to better my understanding of code, as well as practice for some upcoming interviews but I am having trouble understanding running time in Big O. The question was:

You have a staircase with N steps, and you can take any mixture of single and double steps to reach the top. How many different ways can you climb the staircase?

I made a simple answer to the problem

//When the function is first called, I set the second argument, x, to 0
int count_steps(int n, int x){
    if(x==n){
        return 1;
    }
    else if(x>n){
        return 0;
    }
    return count_steps(n, x+2) + count_steps(n,x+1);
}

If someone could either give me an answer, or a good explanation on how Big O works with recursion I would appreciate it. Also if you have any ideas on more efficient solutions I'd appreciate any kind of hint, because I'm working to improve it too.

Answer 1

Let me answer two parts.

1. What is the running time of the OP's original count_steps function?

2. How can the running time be improved?

Since you are always calling initially with X=0, then it's helpful to rewrite the function as:

int count_steps(int n){
    if(n==0){
        return 1;
    }
    else if(n < 0){
        return 0;
    }
    return count_steps(n-2) + count_steps(n-1);
}

Let T(n) be the return value of count_steps for a given value of n:

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

where T(0)=1 and T(-1)=0.

Solve the recurrence T(n)-T(n-1)-T(n-2) = 0. The roots of the characteristic polynomial x^2-x-1=0 are (1+sqrt(5))/2 and (1-sqrt(5))/2

This should look like the Fibonacci sequence. https://en.wikipedia.org/wiki/Fibonacci_number. And it in fact has a closed form solution. T(n)=O(Phi^N) where Phi=(1+sqrt(5))/2 is the golden ratio about equal to 1.618.

Notice that the running time of the function count_steps as originally written, is proportional to the number of times it recurses. (Everything else in the function runs in constant time). Therefore the running time, as originally written is O(T(n)) = O(Phi^n).

How can this be improved? Another answer shows a linear time solution -- which is much better. But since there is a closed form solution to the recurrence (related to finding the Nth Fibonacci number), you can improve your function to O(1).

Answer 2

Memoisation can make an enormous difference:

#include <tuple>
#include <unordered_map>
#include <iostream>
#include <boost/functional/hash.hpp>
#include <chrono>


long long count_steps(long long n){
    if(n==0){
        return 1;
    }
    else if(n < 0){
        return 0;
    }
    return count_steps(n-2) + count_steps(n-1);
}

struct count_steps_algo
{
    using args_type = std::tuple<long long>;
    using result_type = long long;

    template<class Memo, class N>
    result_type operator()(Memo& memo, N&& n)
    {
        if(n==0){
            return 1;
        }
        else if(n < 0){
            return 0;
        }
        return memo(n-2) + memo(n-1);
    }

};

template<class Algo>
struct memoised
{
    using algo_type = Algo;
    using args_type = typename algo_type::args_type;
    using result_type = typename algo_type::result_type;
    using memo_map_type =
    std::unordered_map
            <
                    args_type,
                    result_type,
                    boost::hash<args_type>
            >;

    template<class...Args>
    decltype(auto) operator()(Args&&...args)
    {
        auto i = memo_map_.find(std::tie(args...));
        if (i != memo_map_.end())
        {
            return i->second;
        }
        auto result = algo_(*this, args...);
        memo_map_.emplace(std::tie(args...), result);
        return result;
    }


    Algo algo_;
    memo_map_type memo_map_;

};


int main()
{
    constexpr int N = 45;
    using clock = std::chrono::system_clock;
    auto cs = memoised<count_steps_algo>();
    auto start = clock::now();
    std::cout << "start" << std::endl;
    auto memo_result = cs(N);
    std::cout << "stop" << std::endl;   // compiler optimisation re-orders this on clang!!!
    auto stop = clock::now();
    auto secs = std::chrono::duration<double, std::ratio<1>>(stop - start);

    std::cout << "memoised  : " << memo_result << " took "
              << std::fixed << secs.count() << "s\n";

    auto start2 = clock::now();         // compiler optimisation re-orders this on clang!!!
    std::cout << "start" << std::endl;
    auto raw_result = count_steps(N);
    std::cout << "stop" << std::endl;   // compiler optimisation re-orders this on clang!!!
    auto stop2 = clock::now();
    auto secs2 = std::chrono::duration<double, std::ratio<1>>(stop2 - start2);

    std::cout << "bruteforce: " << raw_result << " took "
              << secs2.count() << "s\n";
}

example output:

start
stop
memoised  : 1836311903 took 0.000082s
start
stop
bruteforce: 1836311903 took 11.026068s