We would like to write a function for computing the value of a polynomial of the form:

The naive way of solving this problem is to substitute the values directly in equation (1) and compute the value of p(x).

The other way is to use Horner's method to compute p(x) as in equation (2). This algorithm is based on a transform and conquer technique.

(a) Implement the naive method and Horner's method to compute the value of a polynomial and test your code to ensure it's working

(b) Experimentally, estimate the running time for each of the methods. Note that you will need to experiment with different values of n. You can use arrays to store values of the coefficients (not zero) and then pick a value for x that is not zero. Create a spreadsheet and graph your results.

Java Eclipse

2 p(x) = 20 +ajx + a2x2 + azx3 + ... + anx" (1) p(x) = ao + x(az + x(a2 + x(az + ... + x(an-1 + xan)... ))) (2)