Design a bruteforce algorithm for computing the value of a p

Design a brute-force algorithm for computing the value of a polynomial p(x) = a_nx^n + a_n - 1^x^n - 1 + ... + a_1 x + a_0 at a given point x_0 and determine its worst-case efficiency class. If the algorithm you designed is in Theta(n^2), design a linear algorithm for this problem.

Solution

Solution of the First Part

//The algorithm computes the value of polynomial P at a given point x

//by the “highest-to-lowest term” brute-force algorithm

//Input: 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

BruteForceEvaluation (P[0..n], x)

x = x₀

p := 0.0

for i = n down to 0 do

      power =1

      for j =1 to i do

             power = power * x

      p = p + a[i] * power

return p

Analysis : We measure the input’s size by the polynomial’s degree n.

The basic operation of this algorithm is a multiplication of two numbers; the number of multiplications M(n) depends on the polynomial’s degree only.

M (n) =ⁿ_i=0 ⁱ_j=11 = _i=0ⁿ=n (n-1)/2= Q(n²)

Or we simple observe that there are two loop (One is outer and another is Inner) so the time complexity of the algorithm is Q(n²)

Efficiency: Q(n²)

Solution of the Second Part

The above algorithm is very inefficient: in these algorithms we recomputed powers of x again and again. As if there were no relationships among them. In the previous algorithm we move from highest to lowest power but now we can move from the lowest term to the highest and compute xⁱ by using xⁱ1.

LinearBruteForcePolynomialEvaluation(P[0..n], x)

x = x₀

p = a[0]

power := 1

for i := 1 to n do

power := power * x

      p := p + a[i] * power

return p

Analysis          The number of multiplications here is M(n) = ⁿ_i=0 2=2n

                                                                                                       =Q(2*n) =Q(n)

              This is Linear.