Problem 1. Consider the problem of evaluating a polynomial p(x) = anx" + an-1x"+ . . . + a1 x + a0. The input is defined bv a value x and a polynomial p represented as an array A - [ao, a1,..., an] of coefficients. The output should be p(x) Assuming each addition and multiplication takes O(1) time, you are to analyze the complexity of two algorithms for this task. The first one, is a naive strategy that computes each term of the polynomial from scratclh 1: function NAivE(x, A) answer 0 3: length of A 2 4: for i from 0 to n do for j from 1 to i do T. answer - answer + aux * Ali return answer The second one, is based on Horner's rule for polynomial evaluation function HORNER(X,A) 1: 2: 3: n=length of A 4: for i from n to 0 do answer = 0 answer - A[i] + answer* x return answer a) Using O-notation, upperbound the running time of NaIvE. b) Using -notation, lowerbound the running time of NAIVE to show that your upperbound is in fact asymptotically tight. c) Using O-notation, upperbound the running time of Horner