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

(a) Provide the pseudocode for a simple O(n 2 ) time method for computing p(x). Justify why your pseudocode executes in O(n 2 ).

(b) Now consider a rewriting of p(x) as p(x) = a0 + x(a1 + x(a2 + x(a3 + . . . + x(an1 + xan). . .))) Provide the pseudocode for computing p(x) using the above formula. Provide the proof of correctness for your algorithm using loop-invariant method. State and justify the time complexity of the algorithm.