1

Can anyone help me finding the time complexity of

T(n)=1 if n<=0 T(n)=T(n-1)+T(n-2)+n

Improve this question
2
  • What are your base cases? n <= 0? Commented Sep 24, 2010 at 22:34
  • zero accepted answers and zero upvotes? no way Commented Sep 24, 2010 at 22:38

2 Answers 2

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

I agree with the conclusion, but I think the proof is wrong: the “i.e.” part is incorrect.
@Svick: It is basic arithmetic! I didn't say it was the fibonacci sequence. The terms are different.
@Moron: Yeah, it basic arithmetic, but (n+1) != (n-1) and you can't just ignore that.
@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.
@svick: btw, sorry about that. I should have been more careful, especially after when you were kind enough to comment.
0

According to OEIS, the closed formula for this function is , which means that the asymptotic complexity of this functions is alt text.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.