What is a non-mathematical explanation for the Big O of recursive fibonacci?
A good number of naive recursive functions have exponential complexity, so this is good intuition to keep in mind.
Consider this function:
function fiboR1(n){
if( n === 0 || n === 1 ){
return n;
} else if ( n >=2 ){
return fiboR1(n-1) + fiboR1(n-1);
}
}
Okay, so fiboR1
doesn't actually compute the Fibonacci sequence. That doesn't matter. Notice that its asymptotic complexity will be at least that of fiboR
. This is because the two recursive calls to fiboR1(n-1)
are more expensive than one call to fiboR(n-1)
and one call to fiboR(n-2)
. So let's think about what the complexity of fiboR1
is.
Let's consider an example call to fiboR1(100)
.
fiboR1(100) = 2 * fiboR1(99)
= 4 * fiboR1(98)
= 8 * fiboR1(97)
= 16 * fiboR1(96)
= 32 * fiboR1(95)
= 64 * fiboR1(94)
...
See the pattern now? We have O(2^n)
recursive calls to fiboR1
, and each call is a constant time branch. So fiboR1
is O(2^n)
, which means that by extension, fiboR
is also O(2^n)
, as big-O is an upper-bound function.
If you know the closed form for the Fibonacci sequence, we can also just do this example for fiboR
directly. Let's consider fiboR(100)
:
fiboR(100) = fiboR(99) + fiboR(98)
= 2 * fiboR(98) + fiboR(97)
= 3 * fiboR(97) + 2 * fiboR(96)
= 5 * fiboR(96) + 3 * fiboR(95)
= 8 * fiboR(95) + 5 * fiboR(94)
= 13 * fiboR(94) + 8 * fiboR(93)
...
The number of recursive function calls follows the Fibonacci sequence. The closed form for the Fibonacci sequence is exponential in n
. In fact, it is O(((1+sqrt{5})/2)^n)
, which is about O(1.6^n)
.
It is simple to calculate by diagraming function calls. Simply add the function calls for each value of n and look at how the number grows.
The Big O is O(Z^n) where Z is the golden ratio or about 1.62.
Both the lenoardo numbers and the fibonacci numbers aproach this ratio as we increase n.
2 (2 -> 1, 0)
4 (3 -> 2, 1) (2 -> 1, 0)
8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
(2 -> 1, 0)
14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
(2 -> 1, 0)
(3 -> 2, 1) (2 -> 1, 0)
22 (6 -> 5, 4)
(5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
(2 -> 1, 0)
(3 -> 2, 1) (2 -> 1, 0)
(4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
(2 -> 1, 0)