« Space complexity analysis for Fibonacci

Space complexity for Fibonacci

Space used by Fibonacci => kn

O(n)

At any given point of time there are maximum n functions waiting in the call stack. Before any new function call adds to the call stack some function will pop out if the stack. fun(n) can't call fun(n-1) and fun(n-2) together. fun(n) has to wait for fun(n-1) to finish before fun(n-2) is called.