Horner's method (polynomial)

[dddx]

Hi again,

Could someone help me out with the following:

Let p(x) be a polynomial of degree n, that is,p(x) = ∑ n i = 0^a i^x^i

a)Describe a simple O(n^2) time method for computing p(x).
(b)Now consider a rewriting of p(x) as p(x) = a0 + x(a1 +x(a2 + x(a3 + ...+ x(an−1 +xan) ... ))),

which is known as Horner's method. Using the big-Oh notation, characterize the number of arithmetic operations this method executes.

All inputs are welcome and appreciated
Thanks in advance.

[DemonWasp]

For everyone who can't read the equation: http://en.wikipedia.org/wiki/Horner_scheme

a) Think about the most direct, brute-force way. That way should be O ( n ^ 2 ). Try it with a small polynomial: p(x) = 1 + 2x + 3x^2 + 4x^3 at x = 2.

b) Think about computing p(x) the rewritten way, starting from the innermost brackets. The algorithm that does that is better than O ( n ^ 2 ), though I'll let you figure out just how much better. Try it with the same small polynomial and x = 2.

[dddx]

DemonWasp @ Wed Sep 21, 2011 2:30 pm wrote:

For everyone who can't read the equation: http://en.wikipedia.org/wiki/Horner_scheme

a) Think about the most direct, brute-force way. That way should be O ( n ^ 2 ). Try it with a small polynomial: p(x) = 1 + 2x + 3x^2 + 4x^3 at x = 2.

b) Think about computing p(x) the rewritten way, starting from the innermost brackets. The algorithm that does that is better than O ( n ^ 2 ), though I'll let you figure out just how much better. Try it with the same small polynomial and x = 2.

Thanks for the great help