javascriptalgorithmdata-structurestime-complexity

I have trouble understanding exponential time complexity


To begin with, here is the main code

 var fib = function(n) {
    if (n===0) return 0
    if (n===2 || n===1) return 1
    return fib(n-1) + fib(n-2)
};   

so the question is to print the Fibonacci number, Now letting go of the logic of the question, I can see that whenever we increase the variable n by 1, the function will be called 2 * n times, so even when we consider backtracking of the function by returning the variables it would be 4 * n major operations, and according to the definition of exponential times time complexity, the number of operations should double every time we increase the input variable and I think it is not the case in here.


Solution

  • For the naive Fibonacci implementation we do indeed find exponential time complexity (or more exactly O(2^n)), most readily apparent by looking at a tree graph of the function calls.

            F_5
       /          \
      F_3         F_4
    /    \      /    \
    F_1  F_2   F_3   F_2
              /   \
            F_2   F_1
    

    You can clearly see how the number of execution doubles in each line (1, 2, 4,...)

    To convince yourself, draw this diagram for F_6 (and F_7 if needed).

    definition of exponential times time complexity, the number of operations should double every time we increase the input variable

    No, exponential time complexity means O(b^n), where n is the length of the input variable. It only doubles each time if b=2. However, you can have b=3 (triples every time), b=4 (quadruples) or b=1.2213, you get the point.

    We can also write code that counts it for us:

    var counter = 0;
    
    function fib(n){
        counter++;    
        if( n <= 1 ){
            return 1;
        }
        return fib(n-1) + fib(n-2);
    }
    
    for( var i = 0; i < 15; ++i ){
        counter = 0;
        fib(i);
        console.log("Fib evaluations for " + i + ": " + counter);
    }
    

    If you do a logarithmic plot of the counter you get the following picture, confirming the exponential increase in execution time:

    enter image description here