*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.'
Poly(1)
sum <-- a_0
for i <-- 1 to n
...product <-- 1
...for j <-- 1 to i
......product <-- product * x
...next j
...sum <-- sum + a_i * product
next i
return sum
Operations count (mults and adds) - assume fast integer registers to handle
loop overheads so can be ignored.
inner most loop 1 mult per trip i trips
outer loop n trips - {sum(i=1 to n) i = n(n+1)/2 mults in the inner loop} + {1
add and 1 multiply per trip =n adds and n mults=2n ops}
Total ops =n(n+1)/2+2n=(n^2)/2+5n/2 ~ (n^2)/2 = O(n^2)
================================================== =======
Poly(2)
sum <-- a_0
product <-- 1
for i <-- 1 to n
...product <-- product * x
...sum <-- sum + a_i * product
next i
return sum
loop contains 3 ops and has n trips so op count is 3n
================================================== ===
Poly (3)
result <-- a_n
for i <-- 1 to n
...result <-- result * x + a_(n-1)
next i
return result
loop has 2 ops and a trip count of n so total ops is 2n.
RonL