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: