USA: +1 (725) 712-1730 
Sign in
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
Expert Answer
There are somany methods for solving
- Use recursion : Exponential
- Optimized : Linear
- 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)
