Validity of time complexity analysis

Question

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 ?

Answer 1

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$.