*EDIT*: Since it didnt indent, I will show indent by *INDENT 1* *INDENT 2*, etc for degree of how much it has to be indented, 1 being first indentation, 2 the 2nd, and so forth.

Suppose we have the polynomial:

a_(n)*x^n + a_(n-1)*x^(n-1) + ... + a_2*x^2 + a_1*x + a_0 for real a_k k = 0, 1, 2, ..., n and x.

We are able to compute the value of the polynomial by using the following 3 algorithms by:

Calculating each term separately, starting with a_0 and adding each of the terms onto an accumulating sum.

First: Poly(1)

sum <-- a_0

for i <-- 1 to n

*INDENT 1*product <-- 1

*INDENT 1*for j <-- 1 to i

*INDENT 2*product <-- product * x

*INDENT 1*next j

*INDENT 1*sum <-- sum + a_i * product

next i

return sum

Second: Poly(2)

Calculating x^k by using the prev. result of x^(k-1) and multip. it by x, instead of recomputing x^k by multip. x by itself k-1 times as in the first part. Like the first part, each of the terms is added to an accumulating sum.

sum <-- a_0

product <-- 1

for i <-- 1 to n

*INDENT 1*product <-- product * x

*INDENT 1*sum <-- sum + a_i * product

next i

return sum

Third: Poly (3)

By clustering successive additions and mult.'s as shown by the following example:

2*x^3 - 7*x^2 + 5*x - 14 = -14 + x*(5 + x*(-7 + x*(2)))

The above is known as Horner's Method.

result <-- a_n

for i <-- 1 to n

*INDENT 1*result <-- result * x + a_(n-1)

next i

return result

QUESTIONS:

a.) For each of the above algorithms, what is the trace for the input?

b.) Determine the total # of operations for the input of the first part, where operations are multiplications and additions.

c.) Let T_i(n) = total # of operations (multiplications and additions) to eval. a polynomial of degree n using Poly(i) for i = 1, 2, 3. Compute T_i(n) for i = 1, 2, 3.

Thanks. I don't think the math is as hard as trying to figure out what to calculate based on the 'pseudocode.'