Given an array A a0 a1 a2 middot middot middot an1 of inte

Given an array A = [a_0, a_1, a_2, * middot middot middot, a_n-1] of integers, let pA be the following polynomial: a_n_ix^n - 1 + a_n - 2^x^n - 2 + middot middot middot + a_2x^2 + a_1x + a_0 Give an algorithm that gets an array A and an integer t as inputs and outputs pA (t) (value of the polynomial at t). Derive the worst-case run-time of your algorithm (as a function of the size of the input array). Your grade will be inversion ally proportional to the run time of your algorithm

Solution

O(n) complexity.

here we use 2 variable one to store x_prev which is initially (1 or x^0) and sum which is initially set to 0.

Traverse the array for each i value of _prev will be x^i

example :

when i =0 x_prev will be 1 x^0

when i =1 x_prev will be x x^1

when i =2 x_prev will be x^2 x^2

...

x_prev=1;

sum=0;

A be the array;

for(int i=0;i<n;i++)

{

sum+=(A[0]*x_prev);

x_prev*=x;

}