What is a non-mathematical explanation for the Big O of recursive fibonacci?

Question

I read both articles on Big O for Recursive Fibonacci sequence but still do not have a conceptual understanding of why it is O(2^n).

This is not a duplicate of this link. Please don't mark as a duplicate. I'm looking for a conceptual answer.

This is one of the simplest recursive functions out there and I want to understand how to look at it and determine the the Big O without complex math and proofs.

// O(2^n)
function fiboR(n){
  if( n === 0 || n === 1 ){
    return n;
  } else if ( n >=2 ){
    return fiboR(n-1) + fiboR(n-2);
  }
}

For example Big O for the iterative version is O(n). I can just look and see that as n increases the while loop iterations increase linearly. No complex math or long proofs needed.

// O(n)
function fibo(n){
  let prev0 = 0;
  let prev1 = 1;
  if( n === 0 || n === 1 ){
    return n;
  }
  while( n-- >= 2){
    sum = prev0 + prev1;
    prev0 = prev1;
    prev1 = sum;
  }
  return sum;
}

Actually that linked question has a really good explanation. — Pointy, Dec 20 '19 at 16:22
@j.a. Yes (both to "do I know or not") and "is it 2^n or 1.6^n". Perhaps this will help: https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation but the dupe question also makes the distinction between its BigO and its tight bound BigO. — Dave Newton, Dec 20 '19 at 16:42
@j.a. because it was wrong :) In this particular case, figuring out the big-O value intuitively without any math is probably a little harder than the math. In one of the answers in the question you linked, there's a link to a video that has a pretty clear (mathematical, but he goes slow) explanation. — Pointy, Dec 20 '19 at 16:44
Well if you get that it's exponential, then the detail of what the exponent base constant is doesn't matter much. That is, in terms of computational cost, 1.6^n is not really a big improvement over 2^n, and in this case there's a linear-time solution that's going to be vastly better than either. — Pointy, Dec 20 '19 at 16:46
@j.a. I've deleted my answer, as I just understood that I've missed the whole point as it all about computation complexity. Sorry, pls read other answers. I was thinking about just math function of fibonacci as such. silly me. — Hero Qu, Dec 20 '19 at 17:28
I've done a bit of testing on how many function calls the recursive fiboR would use for a given N. And not unexpected, there exists already a known sequence for it : [A001595](https://oeis.org/A001595) aka the Leonardo numbers. `a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1.`. Sooo can we call that `O(leonardo(n))` ? ;) — LukStorms, Dec 20 '19 at 19:34

score 2 · Answer 1 · answered Dec 20 '19 at 16:44

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

Hm, rather, both `O(2^n)` and `O(1.6^n)` are valid big-O bounds, since big-O is just an upper bound. `O(1.6^n)` might be a tight bound, but more careful analysis is needed to show that. — GILGAMESH, Dec 20 '19 at 17:03
Could the [A001595](https://oeis.org/A001595) sequence be related to this? — LukStorms, Dec 20 '19 at 19:39
There are no bounds to speak of as the input does not vary. It grows at one rate. And that rate is exponential and the exponent is the golden ratio. — jennifer, Mar 15 '20 at 14:08

score 2 · Accepted Answer · answered Dec 20 '19 at 20:38

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)

score 0 · Answer 3 · answered Dec 20 '19 at 21:05

Assuming you accept that the function is correct, i.e. that it does calculate the Fibonacci numbers, then it is very easy to show that its running time must be exponential: it only returns 0 or 1 in the base case, and it only produces larger results by adding smaller results together.

Since the Fibonacci numbers grow exponentially, the only way you could make them by adding a lot of 1s together is by adding exponentially many 1s. Each result only gets added to the final total once, so the base case must be executed exponentially many times to produce all of those 1s as different results.

What is a non-mathematical explanation for the Big O of recursive fibonacci?

3 Answers3