CareerCup

It is exponential and is a very good example showing how recursion can be bad at times. In such cases memoization is used to memorize what we have already computed and use it in further operations.

Really some good solutions and discussions.

stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence

time complexity: o(n) , as I think we will have to get to 1 from any n, what so ever is given to us.
The space complexity is O(n) too, due to the recursive calls, for n>1 , we have 2 calls to fibo(n-1)and fibo(n-2) i.e. for every n we have 2*n recursive calls. But since we are talking about big O analysis we will not go into constant terms and therefore it is just O(n)

shouldn't this be exponential? 2^n?

n -----------------2^0
/ \
n-1 n-2 -----------------2^1
/ \ / \
(n-1)-1 (n-1)-2 (n-2)-1 (n-2)-2 -----------------2^2


so the complexity is 2^0+2^1+....+2^n which is 2^n

shouldn't this be exponential? 2^n?

n -----------------2^0
/ \
n-1 n-2 -----------------2^1
/ \ / \
(n-1)-1 (n-1)-2 (n-2)-1 (n-2)-2 -----------------2^2


so the complexity is 2^0+2^1+....+2^n which is 2^n

If you see, it is going to generate Binary tree recursively...so 2^n-1

yo its a exponential problem solution sucha a really good example to show how sometimes the recursion is bad for programming just if he memorization is present there then not a problem at all :)