For this question, you need to design, analyze, and implement in $C++$ an algorithm to read an

array $($a$)$ of $(n)$ int values and a value of $(x)$ and find the $p(x)n-$degree polynomial.

You need to calculate the execution time for your two algorithms.

An $n-$degree polynomial $p(x)$ is an equation of the form

$p(x)={\displaystyle \underset{i=0}{\overset{n}{}}}{a}_i{x}^i,$

where $x$ is a constant number and each $a_i$ is an integer number in an array of size $n.$

Your program should implement the following operations:

a$.$ Randomly initialize $n$ as the size of the array.

b$.$ Randomly initialize integer values starting from $0$ and store them in an array $"$a$".$

inputData$($int a$[],$ int $n)$

Call this function to initialize the values of array $"a".$

c$.$ Randomly generate a value for $x$ of any value.

d$.$ Implement a simple $O(n)$ time algorithm for computing $p(x)$ for a particular value of $x.$

e$.$ Implement a simple $O(n^2)$ time algorithm for computing $p(x)$ for a particular value of $x.$

f$.$ Print the time needed to execute each algorithm.

g$.$ Print the value of $p(x).$

Requirements:

A$.$ The program should calculate and print out the value of $p(x)$ using two different algorithms.

The program will measure the time needed to execute the same input but using $2$ different

complex algorithms. You are not allowed to use any built$-$in power function in designing the

algorithms.

B$.$ Your program should perform an experimental analysis of their running times by doing the

following:

For each algorithm, choose at least $5$ appropriate large values for $n,$ where $n$ is the input

array size, and determine how long it takes to run $2$ algorithms in nanoseconds. For

example, value of $,$ etc.$).$

Notes:

Try to choose large values for $n$ to avoid an erratic timing $($e$.$g$.,0$ s or there is no

clear increase in time with respect to input size$).$

You are required to use the same values of $n$ for both algorithms.

C$.$ Your report should include a write up for the following:

$1.$ Explain the two designed algorithms in English sentences or C$++$ pseudocode.

$2.$ Theoretical analysis of the two algorithms in terms of Big$-$O$.$

$3.$ Show and explain the experimental analysis of their running times by displaying the running time for $5$ different n values and by plotting the running times obtained for algorithm $1$ and algorithm $2$ as a function of n as scatter plots on a linear scale.

Justify your answers and compare between theoretical and experimental results.