Jun 122012
 
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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)