Question $5.$Question $1.$

Consider the following polynomial function:

$F(x)={\displaystyle \underset{i=0.n-1}{\overset{?}{}}}A[i]*x^i$

where the array $A[0..n-1]$ is used to store the coefficients.

Write an efficient algorithm $($i$.$e$.,$ pseudo$-$code$)$ to compute the value of $F(x).$

Evaluate $($Array $A[0..n-1]\frac{,}{\text{I}}nt$ egerx $)$

$???$

$???$

$.....$

Analyze the worst$-$case running time of your algorithm $($in terms of $n).$

Remark: You must use primitive operations in your algorithm.

You are not allowed to call library functions like "power" or "exponent".

Insertion$-$Sort $($ Array $A[0..n-1])$

$1.$ for integer ilarr$1ton-1$

$2.$ jlarri

$3.$ while $j>0$ and $A[j-1]>A[j]$

$4.$ swap $A[j]$ and $A[j-1]$

$5.$ jlarrj$-1$

$5($a$)$ Give an example of the worst$-$case input for "Insertion$-$Sort" at $n=8.$

Explain why it is the worst$-$case input.

$5($b$)$ Analyze the worst$-$case running time of "Insertion$-$Sort". Show your steps.