Polynomial problems

[ngolehung84]

Hi,
For this polynomial: a0 + a1*x + a2*x2 +....+ an*xn

I have this algorithm:

S = a0
P = 1
for i=1 to n
P = Px
S = S + ai*P

So S is the result of above polynomial. The running time of this algorithm is O(n). But my feeling tell me that something wrong here!!!!!!

Can you help me out!
Thanks.

[MikeAThon]

Yes, that algorithm seems completely wrong. But it's hard to tell since you use non-standard nomenclature to describe it.

Try starting with an and working your way backwards towards a0.

Mike

[ngolehung84]

Hi MikeAThon,

I really dont know about nomenclature. What does the part of my code make you be confused?

Thanks.

[MaxPower]

I don't see anything wrong with your algo.
But re-writing it in a known language ("nomenclature")
will help people to understand it.
What is your "feeling" telling you something is wrong?
Which line is suspect to you?

[JimK]

Or you can do just that in O(n) time complexity...

S = a0
for i=1 to n
S = S + ai * xi
end

or in C:

S[0]=a[0]
for(i=1;i<n+1;i++)
s[i] = s[i] + (a[i]*x[i])
end

[DavidB]

Hi,
For this polynomial: a0 + a1*x + a2*x2 +....+ an*xn

I have this algorithm:

S = a0
P = 1
for i=1 to n
P = Px
S = S + ai*P

So S is the result of above polynomial. The running time of this algorithm is O(n). But my feeling tell me that something wrong here!!!!!!

Can you help me out!
Thanks.

It looks like pseudo-code for Horner's rule (http://en.wikipedia.org/wiki/Horner%27s_rule), which is a computationally efficient method for evaluating polynomials. It takes n multiplications and n additions, instead of the straightforward way of evaluating one term at a time.

[ngolehung84]

In the book:
Accuracy and Stability of Numerical Algorithms
By Nicholas J. Higham

(You can find it in google book database)
page 104. Problem 5.2 => It said that "give the error analysis ...."

I tried to run step by step many times but I couldn't find any error here.

>> What's the problem? The book is wrong ????

[JimK]

He doesn`t ask from you to find an error.
He asks from you to do an error analysis :D
...as he does after the algorithm of Horner!!!