john-ko / data-structures Goto Github PK

Let see why. Let try fibo(5) and see what happen in the call stack:

                              fib(5)
                           /           \
                  fib(4)       +        fib(3)
              /           \              /         \
          fib(3)  + fib(2)  fib(2) + fib(1)
        /         \
     fib(2) + fib(1)

Basically at each branch you have two choice (two other call) until you reach a known value (2 or 1) so we can say worst case time complexity is O(2^n) or just say exponential

@john-ko

Why not use your LinkedList (or double LinkedList)