How to form Algorithm From Recurrence Relations and Find the Complexity When Negative Terms are Present

Question

I have seen some recurrence relations like

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

This can be simply be converted to some algorithms . But My question here is Can the Recurrence Relations of the form

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

be converted to Algorithm / Code ? If so how ? If not why ?

What will be its complexity ? ie
If T(n-1) is O(n) and T(n-2) is O(2^n) then what will be the complexity ? Will it be of O(n) or O(2^n) If so why does negative term is considered/not considered in finding the complexity

Answer 1

Reccurrence basically is used to model that (mostly time) complexity can be written as a sum when the the algorithm is a sum of it's (partially recursive) steps.

So, for a classic divide-and conquer, you have something like T(n)=2 T(n/2) + c n .

It is possible that you have two terms like in T(n) = T(f(n))+ T(g(n) + h(n), but it is very uncommon to have T(n)=T(n-1) + T(n-2) for two reasons: First, when there is no non-recursive part, the algorithm would be "recursion only". I would expect at least a constant. Second, I can not really imagine an algorithm recursing on a (n-1)-subset and an (n-2) subset of the input.

What I cannot imagine at all is a reason to have a negative part in your recurrence equation. This would be like a part of the algorithm that contributes negative runtime. Don't see how that would be meaningful.

Answer 2

Apply the recursion to T(n-1):

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

Therefore,

T(n) = (T(n-2) - T(n-3) + c(n-1)) - T(n-2) + cn
     = -T(n-3) + c(2n-1)

Apply this recursion to T(n-3):

T(n-3) = -(T(n-6) + c(2(n-3) - 1)) + c(2n-1)
       = -T(n-6) - c(2n - 7) + c(2n - 1)
       = -T(n-6) + 6c

Finally,

T(n) = T(n-6) + 6c

or T(n) = O(n)