Recursive Equation

[nuzzle]

what do you think about it??

I haven't worked much with recurrance relations and I was hoping to be able to solve this one formally but unfortunately I haven't been very successful.

Regarding your solution it looks like you've come up with a Fibonacci tree but that corresponds to only this part of the equation doesn't it?

T(n) = T(n - 1) + T(n - 2)

What I do know is that a Fibonacci tree grows almost as fast as a binary three corresponding to this equation,

T(n) = T(n - 1) + T(n - 1) = 2*T(n-1)

And both have exponential growth so it should be O(c^n) for both.

The question is what happens when you add the n term? I have been able to solve this,

T(n) = 2*T(n-1) + n

and according to my results the dominant term becomes 3*2^n when n grows big. This also means your equation has exponential growth too (because it's bound between two equations with exponential growth), like

T(n) = T(n - 1) + T(n - 2) (lower bound)
T(n) = T(n - 1) + T(n - 2) + n (your equation)
T(n) = 2*T(n-1) + n (upper bound)

So I'm pretty sure Big-O for your equation is O(c^n). I come back if I manage to actually solve it. The problem I'm having is that when I solve it as a second order difference equation the solution I get doesn't correspond to the values you expect when you use the formula as a recurrence relation. I'll try to figure out why this is so.