7. [10 points] A polynomial P(x) with a single indeterminate x is written in the form: P(x) = x) = Σ a¡x¹ = a„x²¹ + a₁-x²¹−¹ + ... + a₂x² + a₁x + ª i=0 where a; for all i € [0, n] is a real constant. Assume that a; = A[i] for all i. We want to compute the univariate polynomial P(x) at a specific value of x. (i) Design a O(n²) algorithm EVALUATE POLY(A[0...n], x) to solve the problem. (ii) Design a O(n log n) algorithm EVALUATE POLY(A[0...n], x) to solve the problem. (Hint: Ideas from the slides are helpful) (iii) Design a O(n) algorithm EVALUATE POLY(A[0...n], x) to solve the problem. (Hint: Use Horner's method of representing the polynomial as follows.) P(x) = a₁ + x(a₁ + x(a₂ + x(A3 + ··· + x(a₂-1 + xan) · · ·)))

Fig: 1