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.


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.

 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>