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

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

Step-by-step 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)