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;
}

Answer 1

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)

Answer 2

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