Search code examples
space-complexity

The space complexity of Fibonacci Sequence

I saw some textbook about the worst-case space complexity of Fibonacci Sequence. However, I have the following question:

enter image description here

Solution

  • You can start with a concrete example and generalize. Start with n = 5.

    S(5) = S(4) + c
     = (S(3) + c) + c
     = ((S(2) + c) + c) + c
     = (((S(1) + c) + c) + c) + c

     = S(1) + 4c

    There are 4 c's when n = 5. In general, there are n-1 c's.