# Question & Answer: Show how one can compute the value of the following recurrence t(n) in O(log n) arithmet…..

Show how one can compute the value of the following recurrence t(n) in O(log n) arithmetic steps using the ideas from the “Perrin Numbers” notes. t(n) = 3 middot t(n – 1) + t(n – 3) – 7 middot t(n – 4), where t(0) = 1, t(1) = 4, t(2) = 8 and t(3) = -2

There are somany methods for solving

1. Use recursion : Exponential
2. Optimized : Linear
3. Further Optimized : Logarithmic

Use recursion : Exponential

// n’th perrin number using Recursion’

#include<stdio.h>

int per(int n)

{

if (n == 0)

return 1;

if (n == 1)

return n-4;

if (n == 2)

return 8;

if (n == 3)

return -2;

return 3*per(n-1) + per(n-3)-7*per(n-4);

}

// Driverr code

int main()

{

int n = 9;

printf(“%d”, per(n));

return 0;

}

```After sloving the value is : -2826
```

per(8)

/

per(6)             per(5)

/                   /

per(4)      per(3)        per(3)    per(2)

/             /            /

per(2)   per(1) per(1) per(0) per(1) per(0)