Manually calculating time complexity of recursive Fibonacci algorithm

Question

I am trying to understand the time complexity of the recursive Fibonacci algorithm.

fib(n)
    if (n < 2)
        return n
    return fib(n-1)+fib(n-2)

Having not much mathematical background, I tried computing it by hand. That is, I manually count the number of steps as n increases. I ignore all things that I think are constant time. Here is how I did it. Say I want to compute fib(5).

n = 0 - just a comparison on an if statement. This is constant.
n = 1 - just a comparison on an if statement. This is constant.
n = 2 - ignoring anything else, this should be 2 steps, fib(1) takes 1 step and fib(0) takes 1 step.
n = 3 - 3 steps now, fib(2) takes two steps and fib(1) takes 1 step.
n = 4 - 5 steps now, fib(3) takes 3 steps and fib(2) takes 2 steps.
n = 5 - 8 steps now, fib(4) takes 5 steps and fib(3) takes 3 steps.

Judging from these, I believe the running time might be fib(n+1). I am not so sure if 1 is a constant factor because the difference between fib(n) and fib(n+1) might be very large.

I've read the following on SICP:

In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.

In this case, I believe the number of nodes in the tree is fib(n+1). So I am confident I am correct. However, this video confuses me:

So this is a thing whose time complexity is order of actually, it turns out to be Fibonacci of n. There's a thing that grows exactly as Fibonacci numbers. 

...

That every one of these nodes in this tree has to be examined.

I am absolutely shocked. I've examined all nodes in the tree and there are always fib(n+1) nodes and thus number of steps when computing fib(n). I can't figure out why some people say it is fib(n) number of steps and not fib(n+1).

What am I doing wrong?

Answer 1

In your program, you have this time-consuming actions (sorted by time used per action, quick actions on top of the list):

• Addition
• IF (conditional jump)
• Return from subroutine
• Function call

Lets look at how many of this actions are executed, and lets compare this with n and fib(n):

 n | fib | #ADD | #IF | #RET | #CALL  
---+-----+------+-----+------+-------
 0 |   0 |    0 |   1 |    1 |     0
 1 |   1 |    0 |   1 |    1 |     0

For n≥2 you can calculate the numbers this way:

• fib(n) = fib(n-1) + fib(n-2)
• ADD(n) = 1 + ADD(n-1) + ADD(n-2)
• IF(n) = 1 + IF(n-1) + IF(n-2)
• RET(n) = 1 + RET(n-1) + RET(n-2)
• CALL(n) = 2 + CALL(n-1) + CALL(n-2)

Why?

• ADD: One addition is executed directly in the top instance of the program, but in the both subroutines, that you call are also additions, that need to be executed.
• IF and RET: Same argument as before.
• CALL: Also the same, but you execute two calls in the top instance.

So, this is your list for other values of n:

  n |    fib |   #ADD |    #IF |   #RET |  #CALL  
 ---+--------+--------+--------+--------+--------
  0 |      0 |      0 |      1 |      1 |      0
  1 |      1 |      0 |      1 |      1 |      0
  2 |      1 |      1 |      3 |      3 |      2
  3 |      2 |      2 |      5 |      5 |      4
  4 |      3 |      4 |      9 |      9 |      8
  5 |      5 |      7 |     15 |     15 |     14
  6 |      8 |     12 |     25 |     25 |     24
  7 |     13 |     20 |     41 |     41 |     40
  8 |     21 |     33 |     67 |     67 |     66
  9 |     34 |     54 |    109 |    109 |    108
 10 |     55 |     88 |    177 |    177 |    176
 11 |     89 |    143 |    287 |    287 |    286
 12 |    144 |    232 |    465 |    465 |    464
 13 |    233 |    376 |    753 |    753 |    752
 14 |    377 |    609 |   1219 |   1219 |   1218
 15 |    610 |    986 |   1973 |   1973 |   1972
 16 |    987 |   1596 |   3193 |   3193 |   3192
 17 |   1597 |   2583 |   5167 |   5167 |   5166
 18 |   2584 |   4180 |   8361 |   8361 |   8360
 19 |   4181 |   6764 |  13529 |  13529 |  13528
 20 |   6765 |  10945 |  21891 |  21891 |  21890
 21 |  10946 |  17710 |  35421 |  35421 |  35420
 22 |  17711 |  28656 |  57313 |  57313 |  57312
 23 |  28657 |  46367 |  92735 |  92735 |  92734
 24 |  46368 |  75024 | 150049 | 150049 | 150048
 25 |  75025 | 121392 | 242785 | 242785 | 242784
 26 | 121393 | 196417 | 392835 | 392835 | 392834
 27 | 196418 | 317810 | 635621 | 635621 | 635620

You can see, that the number of additions is exactly the half of the number of function calls (well, you could have read this directly out of the code too). And if you count the initial program call as the very first function call, then you have exactly the same amount of IFs, returns and calls.

So you can combine 1 ADD, 2 IFs, 2 RETs and 2 CALLs to one super-action that needs a constant amount of time.

You can also read from the list, that the number of Additions is 1 less (which can be ignored) than fib(n+1).

So, the running time is of order fib(n+1).

The ratio fib(n+1) / fib(n) gets closer and closer to Φ, the bigger n grows. Φ is the golden ratio, i.e. 1.6180338997 which is a constant. And constant factors are ignored in orders. So, the order O(fib(n+1)) is exactly the same as O(fib(n)).

---

Now lets look at the space:

It is true, that the maximum space, needed to process a tree is equal to the maximum distance between the tree and the maximum distant leaf. This is true, because you call f(n-2) after f(n-1) returned.

So the space needed by your program is of order n.