Check if parenthesis are matched or not
June 12, 2012Difference between linked list and Arrays
June 12, 2012Compute polynomial, Cn.x^n + Cn-1.x^(n-1) + … … + C2.x^2 + C1.x + C0
Write an effective algorithm to compute the value of below polynomial for a given value of x :
F(x) = Cn.xn + Cn-1.xn-1 + Cn-2.xn-2 + … … + C3.x3 + C2.x2 + C1.x + C0
The normal function to compute this will take O(n2) time. But your algorithm should not take more than O(n) time.
Solution:
Brute-Force Method:
The brute-force method to compute the polynomial is as follows:
int compute(int *c, int n, int x)
{
int sum =0;
for(int i=0; i<n; i++)
{
int prod = 1;
// computing x^i
for(int j=0; j<=i; j++)
prod *= x;
sum += c[i] * prod;
}
return sum;
}
But the time complexity of above algorithm is O(n2).
Optimized method: (Horner’s Method):
The problem with the above algorithm is that we are computing xi every time for each value of i. which is taking O(i) time. But if we already have computed ,say, x5 then computing x6 is a simple O(1) operation multiply it by just one x. Horner’s method uses this technique.
In this method we will write the below polynomial
as shown below
The algorithm will change as shown below:
int compute(int *C, int n, int x)
{
int sum = C[n-1];
for(int i=n-2; i>=0; i--)
{
sum *= x;
sum += C[i];
}
return sum;
}
The above function clearly takes O(n) time.