Question

. Consider the following brute-force algorithm for evaluating a polynomial. ALGORITHM Brute Force Polynomial Evaluation(P[0..n], x) //Computes the value of polynomial P at a given point x //by the "highest to lowest term" brute-force algorithm //Input: An array P[0..n] of the coefficients of a polynomial of degree n, // stored from the lowest to the highest and a number x //Output: The value of the polynomial at the point x p ← 0.0 for in downto 0 do power ← 1 for j ← 1 to i do power ← power ∗ x p ← p + P[i] ∗ power return p Find the total number of multiplications and the total number of additions made by this algorithm.

Answer 1

Answer:

The answer of the the following question are 0(n^2)

The total number of multiplication is 2

And the total number of addition is 1

Explanation:

Let the size of the input is the degree of the polynomial = "n"

Than the number of the multiplications depends on "n"

Let the number of multiplication = M(n)

Let the number of addition = A(n)

1): Solution-

M(n) = n∑_{i=0}          i∑_{j=1}          2

= 2     n∑_{i=0}           i∑_{j=1}  

= 2      n∑_{i=0}      i-1+1

= 2      n∑_{i=0}     i

= 2  *  n*(n+1)/2    =   n*(n+1)

= n^2 + n ∈ 0(n^2)

2): Solution for addition-

A(n) = n∑_{i=0}          i∑_{j=1}          1

= by solving this from the same way it leads to

= n^2 + n   and n^2 + n ∈ 0(n^2)