(1) Suppose you want to have a program that evaluates polynomials. (a) Here's (presumably) the simplest...

   

Transcribed Image Text:

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