(1) Suppose you want to have a program that evaluates polynomials. (a) Here’s (p

Question

(1) Suppose you want to have a program that evaluates polynomials. (a) Here’s (presumably) the simplest possible program. Input: polynomial p(x) = a0 + a1x + a2x 2 + · · · + anx n n, the degree , a real number Output: p() (the value of p at x = ) Return( a0 + a1 · + a2 · 2 + · · · + an · 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 12 and later 13 from scratch? Write pseudocode that saves compuation time by looping through the terms of the polynomial, calculating successive powers of more efficiently. What is its asymptotic time complexity?

Explanation / Answer

We can use Horners rule to evaluate a polynomial in O(N) time

Algorithm Horners(A , n, t )

Start
result = A[1]

    for i=2 to n

        result = result*t + A[i]

    return result

End

Let us understand , how it does the evaluation

Consider a polynomial 2x3 - 6x2 + 2x - 1

So A will contain [ 2, -6, 2, -1 ]

n is equal to 4,

The Polynomial will be evaluated in the form =>

((2x – 6)x + 2)x – 1.


Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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