6. Given coefficients a0, a1,..., an E N, consider the polynomial: () n () = k=0 alding (6) For this problem, assume that addition and multiplication of two natural numbers takes only O(1) time (regardless of how large they are). (lucy (a) Describe a naive algorithm that, given [ao, a1,..., an] and r computes p(x). Give an analysis of its runtime as a function of the degree n of the polynomial. (b) As an alternative, we can compute the polynomial via following expression: p(x)=ao+x (a1+x (a2++ (an-1+x an))). . . . Describe and analyze an algorithm that evaluates the polynomial using the above ex- pression. The runtime should be a function of n as well. Suppose that A and B are languages over alphabet . Answer the number of the correct definition. Function f is a polynomial-time mapping reduction from A to B provided 1. f: A B, f is computable in polynomial time and, for all x A (x = B f(x) = A). 2. f:**, f is computable in polynomial time and, for all x = * (f(x) = A f(x) = B). 3. f: A B, f is computable in polynomial time and, for all x =* (XE B >> f(x) = A). 4. f:**, f is computable in polynomial time and, for all x * (x = A >>> f(x) = B).