Analysis of Algorithms

• 03-29-2013, 09:45 AM
rhym1n
Analysis of Algorithms
I haven't taken a programming class yet and this question really confuses me, any help is greatly appreciated.

The following pseudocode procedure can be used to evaluate the polynomial 8 – 10x + 〖7x〗^2 - 〖2x〗^3 + 〖3x〗^4 + 〖12x〗^5, when x is replaced by an arbitrary (but fixed) real number r. For this particular instance, n = 5 and a_0 = 8, a_1 = -10, a_2 = 7, a_3 = -2, a_4 = 3, and a_5 = 12.
Code:

```        procedure PolynomialEvaluation1           (n: nonnegative integer;           r, a_0, a_1, a_2,…, a_n: real)         begin           product := 1.0           value := a_0           for i := 1 to n do               begin                 product := product * r                 value := value + a_i * product               end         end```
How many additions take place in the evaluation of the given polynomial? (Do not include the n – 1 additions needed to increment the loop variable i.) How many multiplications?
• 03-29-2013, 10:28 AM
JosAH
Re: Analysis of Algorithms
That is Horner's rule: for a polynomial a(n)*x^(n) +a(n-1)*x^(n-1) + ... a(0), the polynomial can be rewritten as: x*(a(n)*x^(n-1) ... a(1))+a(0). If you recursively apply this rule to the polynomial (of lower degree) you can see that it takes n-1 multiplications and n-1 additions to evaluate the entire polynomial.

kind regards,

Jos
• 03-29-2013, 07:17 PM
rhym1n
Re: Analysis of Algorithms
Hmm, interesting and thank you. I am still having trouble finding how many additions and multiplications total.
• 03-29-2013, 07:37 PM
JosAH
Re: Analysis of Algorithms

kind regards,

Jos
• 03-29-2013, 08:03 PM
rhym1n
Re: Analysis of Algorithms
Oh sorry. I read that as soon as I woke up and things didn't click lol. My bad.

Thank you again!
• 03-29-2013, 08:47 PM
JosAH
Re: Analysis of Algorithms
Quote:

Originally Posted by rhym1n
Oh sorry. I read that as soon as I woke up and things didn't click lol. My bad.

Thank you again!

You're welcome and the only things that click when I wake up are the on/off switch of my espresso machine and my llghter for my first sigaret of the day ;-)

kind regards,

Jos