MCN Professionals | Interview Question of the day
MCN Professionals is starting Industrial Training for MCA-2012 Batch. Have a look at our Industrial Training Program and Course Details.
-----------------------------------------------------------------------------------------------------------------------------------------
Today's Question:
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(n^2) time. But your algorithm should not take more than O(n) time.
Solution:
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).
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
Now 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.
---------------------------------------------------------------------------
Interview Questions Archive:
To see all the questions in the category click
here...