Let p$($x$)$ be a polynomial of degree n$,$ that is$,$ p$($x$)=$ Pn

i$=0$ aixi.

$($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$)=$ a$0+$ x$($a$1+$ x$($a$2+$ x$($a$3+...+$ x$($an$1+$ xan$)...)))$

$.$

Provide the pseudocode for computing p$($x$)$ using the above formula. Provide the proof of cor$-$

rectness for your algorithm using loop$-$invariant method. State and justify the time complexity

of the algorithm.