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.
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: