Let p(x) be a polynomial of degree n, that is, p(x) = n i=0 a i

Let p(x) be a polynomial of degree n, that is, p(x) = Σⁿ_i=0 a_ixⁱ.

a. Describe a simple O(n²)-time algorithm for computing p(x).

b. Describe an O(nlogn)-time algorithm for computing p(x), based upon a more efficient calculation of xⁱ.

c. Now consider a rewriting of p(x) as

p(x) = a₀+x(a₁+x(a₂+x(a₃+···+x(a_n−1+xan) ···))),

which is known as Horner’s method. Using the big-Oh notation, characterize the number of arithmetic operations this method executes.