2

Below is a recurrence relation

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

If it is possible then what would be its pseudocode?

lets take an example-

main()
{
int n=9;
int result1 = fact(n-1);
int result2 =fact(n-2);
}

function int fact(int n)
{
if(n==0)
return 1;
else
return n*fact(n-1);;
}

here recurrence relation will be T(n) = T(n-1) + T(n-2)

But what would be the pseudo code for T(n) = T(n-1) - T(n-2)?

Anurag Chakraborty
  • 421
  • 2
  • 5
  • 20
  • duplicate http://stackoverflow.com/questions/3209303/is-there-such-a-thing-as-negative-big-o-complexity ? – sve Oct 06 '15 at 18:49
  • 1
    in short, you can't since by definition of complexity of a program you have to add operation counts. – sve Oct 06 '15 at 18:50
  • I've gone through that answer but that didn''t clarify my doubts. If it's not possible then is this type of recurrence relation restricted only for theory not for pseudocode? – Anurag Chakraborty Oct 06 '15 at 18:55
  • 2
    Half the answers are to the question "what's the pseudocode for the recurrence relation $F_n = F_(n-1) - F_(n-2)$" rather than the idea of hypothetical runtime, so even if you edit this to be clear it will have misleading answers – Pete Kirkham Oct 06 '15 at 21:59
  • Echoing @Pete, I initially thought this question had more to do with numerical analysis / numerical optimization methods (eg gauss-seidel) or number theory. – Brian Vandenberg Oct 06 '15 at 22:46

4 Answers4

2

It looks like an impossibility. Let equation 1 be:

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

and equation 2 be:

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

Adding equations 1 and 2 gives,

T(n) = - T(n-3)

So either, T(n) = T(n-3) = 0 or alternatively, this recurrence is impossible to code.

displayName
  • 13,888
  • 8
  • 60
  • 75
  • yeah, absolutely weird, I upvoted you, because you're right! – Pavel Oct 06 '15 at 20:22
  • @paulpaul1076: Deeply appreciate it. Thank you. :D – displayName Oct 06 '15 at 20:32
  • Why impossible to code? It actually trivializes the code to the extent that recursion function is not needed to be implemented any more. Your result, T(n)=-T(n-3), implies that T(6k) = T(0), T(6k+1)=T(1), T(6k+2)=T(2), T(6k+3) = -T(0), T(6k+4)=-T(1), T(6k+5)=-T(2), for k=0,1,2,.. So, given any n>=0, the function just needs to return one of the 6 different constants depending on mod(n,6). – norio Aug 18 '23 at 04:33
  • @norio: I think you are right - It is not impossible to code, rather it is a trivial "base case". – displayName Aug 26 '23 at 15:31
2

Recurrence relations can be used for a lot of things, not only complexity estimation.

But as for complexity estimation you are surely misusing them when you get a recurrence relation such as T(n) = T(n-1) - T(n-2).

Of course you can write a program such as:

function fib(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 1;

    return fib(n-1) - fib(n-2);
}

but note that you will still have to add up calls from fib(n-1) to fib(n-2), because you call them, so your recurrence relation for T(n) = T(n-1) - T(n-2) doesn't make sense for programs.

As for the example given by Eric J., he gave a formula that calculates something, however the complexity of the program I gave above is still O(2^n), because you have to add operation counts, as svs said in the comments.

              fib(n)
               /\
        fib(n-1) fib(n-2)
           /\       /\
   fib(n-2)  fib(n-3) fib(n-4)
...............................

The above is a function calling graph for both cases regardless of whether there's a minus in between or not.

PS: I didn't mean to have 2 edges going into fib(n-3), i wanted to write fib(n-3) separately, but I guess it looks better this way.

The program above does not calculate Fibonacci sequence, I only modified it by putting a minus there.

Pavel
  • 1
  • 3
  • 17
  • 51
1

Assuming n >= 0:

// base cases
T(0) :
  return T0
T(1) :
  return T1

// recurrence relation
T(n) :
  return T(n-1) - T(n-2)

The first few terms are:

0:  T0
1:  T1
2:  T1 - T0
3:  -T0
4:  -T1
5:  -T1 + T0
6:  T0
7:  T1

... which boils down to:

U(0) = U0
U(1) = U1
U(2) = U1 - U0
// borrowing from @displayName's answer
U(n) = -U(n-3)
// or
T(n) = (-1)^(floor(n/3)) * U(mod(n,3))

The (-1)^floor(n/3) term will cause it to alternate such that sign(T(n)) is positive when floor(n/3) is zero or an even number, and negative otherwise. mod(n,3) makes it repeat the sequence.

Brian Vandenberg
  • 4,011
  • 2
  • 37
  • 53
  • Not only did I give valid pseudo-code in the 1st block of code for the original recurrence relation, the last block also gives pseudo-code for calculating the recurrence, reduced to a form that doesn't directly refer to any terms in the sequence. My point is: it can be done, and here's pseudo code demonstrating that. – Brian Vandenberg Oct 06 '15 at 21:52
  • 2
    @paulpaul1076 he's given the psuedocode for the recurrence relation T(n) = T(n-1) - T(n-2), as per the question, rather than pseudocode for a relation whose run time is expressed by the given recurrence relation . It's not a well phrased question at all. – Pete Kirkham Oct 06 '15 at 21:55
  • @PeteKirkham oh, that's true, I was thinking about the complexity, anyways you're right, it's very convoluted. – Pavel Oct 06 '15 at 22:07
0

Sure, this is probably most widely known from calculating the Fibonacci Sequence

You start with

0, 1

and get subsequent terms by adding the previous two terms.

T(2) = T(1) + T(0) T(2) = 1

0, 1, 1

T(3) = T(2) + T(1) T(3) = 1 + 1 = 2

0, 1, 1, 2

But what would be the pseudo code for T(n) = T(n-1) - T(n-2)

Here's code for the Fibonacci sequence T(n) = T(n-1) + T(n-2). If you wanted instead to subtract terms as in your example, just change + to -.

function fib(int n)
{
    if (n == 0) return 1;
    if (n == 1) return 1;

    return fib(n-1) + fib(n-2);
}
Eric J.
  • 147,927
  • 63
  • 340
  • 553
  • negative in the sense how can there be minus sign in between two recurrence i.e T(n-1) & T(n-2)? – Anurag Chakraborty Oct 06 '15 at 18:52
  • 1
    That all depends on how you index your terms. 0-based arrays is a useful convention but not the only imaginable one. As long as T(-1) means something to the algorithm, sure you could have actually negative terms. – Eric J. Oct 06 '15 at 19:13
  • I provided an implementation for calculating the Fibonacci sequence with recursion. Note that each call to fib() for n >= 2 results in *two* recursive calls. As a side note, I used this as an interview question for a while. – Eric J. Oct 06 '15 at 19:37
  • @EricJ. but the that's the recurrence relation for that sequence and not for the program though. – Pavel Oct 06 '15 at 20:29
  • 2
    So you are saying `return fib(n-1) - fib(n-2);` will have recurrence relation `T(n) = T(n-1) - T(n-2)`. But technically shouldn't it still be `T(n) = T(n-1) + T(n-2)`? – Anurag Chakraborty Oct 07 '15 at 06:21