1. Member Join Date
Feb 2013
Posts
32
Rep Power
0

## 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.
Java 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?  Reply With Quote

2. ## 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  Reply With Quote

3. Member Join Date
Feb 2013
Posts
32
Rep Power
0

## Re: Analysis of Algorithms

Hmm, interesting and thank you. I am still having trouble finding how many additions and multiplications total.  Reply With Quote

4. ## Re: Analysis of Algorithms

kind regards,

Jos  Reply With Quote

5. Member Join Date
Feb 2013
Posts
32
Rep Power
0

## 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!  Reply With Quote

6. ## Re: Analysis of Algorithms 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  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•