Question

Consider the following algorithm (known as Horner's rule) to evaluate f(x) = sigma_i=0^x a, x^i; poly = 0; for(i=n; i>=0; i--) poly = x * poly + a_i a. Show how the steps are performed by this algorithm for x = 3, f(x) = 4x + 8x + x + 2. b. Explain why this algorithm works. c. What is the running time of this algorithm?

Answer 1

a) f(x)=4x+8x+x+2 for x=3

= 2+x(4+8+1)

= 2+3(13)

= 2+39 =41

b) To convert between different positional of numeral systems we will use this method. In this method, case x is the base of the number system, and the a_i coefficients are the digits of the x representation for a given number. And can also be used if x is a matrix, where the gain in computational efficiency is large. Actually, when x is a matrix, further acceleration is possible where we look deep into the structure of matrix multiplication, where only {\displaystyle {\sqrt {n}}}instead of n multiplies are needed (at the expense of requiring more storage)

c) O(n)= as we go with polynomial equation