Question

f(x) = 2.10 Consider the following algorithm (known as Horner's rule) to evaluate -ax': poly = 0; for( i=n; i>=0; i--) poly = x * poly + ai 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

Solution:

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 system. In this method , case x is the base of number system, and the a_i coefficients are the digits of the x representation for given number. if x is the matrix, then gain in computational efficiency is large, when x is a matrix, further acceleration is possible ,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.

******************************************......................................................*******************************