Check if parenthesis are matched or not
June 12, 2012
Difference between linked list and Arrays
June 12, 2012

Compute 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

horners_1.jpg

as shown below

Horners_2.jpg

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.

Leave a Reply

Your email address will not be published. Required fields are marked *