Computer Science Canada

Horner's method (polynomial)
Author:  dddx [ Wed Sep 21, 2011 1:49 pm ]
Post subject:  Horner's method (polynomial)
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.
Author:  DemonWasp [ Wed Sep 21, 2011 2:30 pm ]
Post subject:  RE:Horner\'s method (polynomial)
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.
Author:  dddx [ Wed Sep 21, 2011 11:42 pm ]
Post subject:  Re: RE:Horner\'s method (polynomial)
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 Smile

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy