Consider evaluating a polynomial

QUESTION

Consider evaluating a polynomial

eg:

f(x) = x⁵ + 3x² – x + 2

f(2) = 44

Considering the general case, where the degree of the polynomial is n, state (i) naive algorithm  (ii) a linear algorithm to evaluate polynomials for a given real-valued input. What is the type of this linear algorithm?

SUMMARY

The polynomial is known in terms of its coefficient and degree. This polynomial is to be evaluated for a particular value. To evaluate this, an algorithm is written. The algorithm for this can be written in two ways: one using the naïve approach and the other using an efficient algorithm having linear time complexity. (linear algorithm)

EXPLANATION

It is given that the degree of the polynomial is ‘n’.

If the polynomial is f(x) and ‘p’ be the parser integer which is parsed to f, to find f(p).

 coeff[] —> the array consisting of coefficient of the polynomial.

ALGORITHM

a) Naïve algorithm

Function evaluatePolynomial (int n, int p, int coeff[n])

      Assign 0 to S

      For every j from 0 to n

              S <- (S + coeff[j]*(p**j))

      Return S

(S = sum)

The above algorithm looks linear but is not actually linear. p**j indicates the power operation which means pj, for which again linear time would be taken. Therefore, it would become O(n²) time.

Instead of doing exponentiation operation in every loop the previous term can be is stored somewhere and this will prevent the need of doing exponentiation operations that many number times.

The value p⁰ is first stored in a variable ‘y’ and in the next iteration x will be multiplied with ‘p’, likewise, only one multiplication will be done for each iteration.

b) Linear algorithm

Function evaluatePolynomial (int n, int p, int coeff[n])

      Assign 0 to S

      Assign 1 to y

      For every j from 0 to n

              S <- (S + coeff[j]*y)

              y = y*p

      Return S

The time complexity of the above algorithm is O(n).

Also read, design, and implement (i.e write a program) an algorithm that adds two polynomials