Can anyone help me finding the time complexity of
T(n)=1 if n<=0 T(n)=T(n-1)+T(n-2)+n
, which means that the asymptotic complexity of this functions is 
.
+2
A:
Consider
F(n) = T(n) + n + 3.
This gives us
F(n) - (n+3) = F(n-1) - (n-1+3) + F(n-2) - (n-2+3) + n
i.e
F(n) - 3 = F(n-1) - 2 + F(n-2) - 1
i.e
F(n) = F(n-1) + F(n-2)
which is a Fibonacci like sequence!
It is well known that for fibonacci like sequences, F(n) = Theta(phi^n) where phi is the golden ratio.
Moron
2010-09-25 22:46:42
I agree with the conclusion, but I think the proof is wrong: the “i.e.” part is incorrect.
svick
2010-09-26 13:33:48
@Svick: It is basic arithmetic! I didn't say it was _the_ fibonacci sequence. The terms are different.
Moron
2010-09-26 13:40:01
@Moron: Yeah, it basic arithmetic, but `(n+1) != (n-1)` and you can't just ignore that.
svick
2010-09-26 14:47:39
@svick: You are right! I have edited the answer. Thanks for pointing the error. I do need new eyes! To be fair (to myself I suppose :-)), those constant terms can be ignored when talking about BigOh. i.e F(n) = F(n-1) + F(n-2) + K has same asymptotics as fibonacci.
Moron
2010-09-26 16:31:55
@svick: btw, sorry about that. I should have been more careful, especially after when you were kind enough to comment.
Moron
2010-09-26 16:37:29
@Moron: No problem.
svick
2010-09-26 17:49:21