# Validity of time complexity analysis

Given recurrence equation :

$$T(N) = T(N-1) + T(N-2) + N$$

Given base case

$$T(1) = -3$$

So I rewrote the equation as

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

Substituting $$V(n) = T(n) + n - T(1)$$ we get :

$$V(n) = V(n-1) + V(n-2)$$

which is the Fibonacci relation , hence :

$$T(n) = \frac{\phi^{n} - \psi^{n}}{\sqrt {5}} +n-3$$

where $$\phi$$ is the golden ratio.

Is the substitution correct theoretically as asymptotically the constant term is dominated by the linear term ?

• Fix the first recurrence (equivalent to $0=T(n-1)+n$) which is obviously not the intended one.
– user16034
Sep 5 at 15:31
• We discourage "please check my work - is it correct?" questions here, as they are unlikely to be of any use to others in the future. We are trying to build an archive of knowledge that will be useful to others. See here and here. Can you ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on.
– D.W.
Sep 5 at 15:52
• @D.W. I tried a more focused approach, is it a useful way to ask? Sep 5 at 16:11

Your substitution is correct and indeed leads to Fibonacci. Anyway the final answer does not respect $$T(1)=-3$$ and there is a sign error.

I would prefer to rework the recurrence independently of $$T(1)$$, writing

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

or $$U(n)=U(n-1)+U(n-2)+3$$

then

$$U(n)+3=U(n-1)+3+U(n-2)+3$$ and

$$V(n)=V(n-1)+V(n-2).$$

The general solution is thus

$$V(n)=U(n)+3=T(n)+n+3=aF_n+bF_{n-1}$$ where $$F_{-1}=1$$.

Only now do we introduce the known initial condition $$V(1)=1$$, which gives $$a=1$$ and $$b$$ free.

Hence,

$$T(n)=F_n+bF_{n-1}-n-3.$$

Regarding the asymtotic behavior, we have two cases.

• if $$b\ne-\phi$$, $$T(n)\sim\left(1+\dfrac b\phi\right)F_n$$ and the behavior is geometric of common ratio $$\phi$$,

• if $$b=-\phi$$, the growing $$\phi$$ exponential cancels out and $$T(n)\sim-n-3$$.