Suppose you want to have a program that evaluates polynomials. Suppose you want

Question

Suppose you want to have a program that evaluates polynomials.

Suppose you want to have a program that evaluates polynomials. (a) Here's (presumably) the simplest possible program. Input: polynomial p(x) = a_0 +a_1x + a_2x^2 + ... + a_nx^n n, the degree alpha, a real number Output: p(alpha) (the value of p at x = alpha) Return (a_0 + a_1 middot alpha + a_2 middot alpha^2 + ... + a_n middot alpha^n) How many additions and multiplications occur when this code is run? What is the asymptotic time complexity? (Important: exponentiation does not count as an "atomic operation"; you need to count the number of multiplications needed.) (b) The above is pretty wasteful; why should the computer calculate alpha^12 and later alpha^13 from scratch? Write pseudocode that saves compilation time by looping through the terms of the polynomial, calculating successive powers of a more efficiently. What is its asymptotic time complexity? Remark: there is an even more efficient algorithm. "Horner's Rule." It is slightly faster than the suggested algorithm in (lb).

Explanation / Answer

No. of additions = n

No. of multiplication = (n+1)(n+2)/2

Asymptotic complexity = O(n^2).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.