$[5$ pts$.]$ Formally show that the function

$f(n)={\displaystyle \underset{i=1}{\overset{n}{}}}{i}^2$

is $O(n^3).[6$ pts$.]$ Consider the following pseudocode of an algorithm for an operation on a sequence

dataset of $n$ real$-$valued numbers $a_0,a_1,$dots,$a_{n-1},$ given as input to the algorithm in $n-$element

array A representation such that each element $A[i]=a_i$ for all $i=0,1,$dots,$n-1.$

$($a$)$ What is the algorithm for Operation computing?

$($b$)$ Provide a tight big$-$Oh running$-$time and space characterization of Operation in terms

of $n.$ Briefly justify your answer. $[10$ pts$.]$ Detecting anomalies in a data set is an important task in data science. One

approach to anomaly detection involves the detection, retrieval, and analysis of outliers. A

useful sub$-$routine for an algorithm to compute outliers is a function that extracts all the

elements of an array $A$ of $n$ numbers that are smaller than a given value $x$ or larger than

another given value $y,$ all given as input, and returns the elements in A that are in those lower

and upper regions $($i$.$e$.,$ outside an interval range$)$ of the real$-$line using a sorted$/$ordered list

data structure. Let us call an algorithm for this function FindOutside.

$($a$)$ Provide an efficient algorithm, in pseudcode, for the function FIndOutside described

above: complete the step$-$by$-$step by writing down the missing statements, already

started for you below. Assume that you have available an implementation of the sorted$-$

list ADT which includes the method inSERT which, taking as input an element, inserts

the element in the proper position in the sorted list, and does so in linear time and

constant space. $($Make sure to use indentation to clearly indicate the proper scope of

each statement.$)$

Algorithm $2$ FindOutSide $(\}$A$,$x$,$y

L $\backslash$leftarrow new sorted list initially empty

$2$:

$3$:

$4$:

return L

$($b$)$ Give a tight big$-$Oh time and space characterizations in terms of $n,$ of the algorithm

FindOutside. Justify your answer. Assume the implementation of the insert operation

takes time linear in the size of the sorted list and uses a constant amount of space.$[5$ pts$.]$ Show that $3n^3-8n^2+7nlogn-4$ is $O(n^3).$ Justify your answer by a providing

real$-$valued constant, corresponding to the upper$-$bound constant factors $c,$ and the integer

constant $n_{0}1,$ consistent with the definition of big$-$Oh$.($Show your work. The provided

constants $c,$ and $n_0$ should follow clearly from your work and be reasonably tight.$)$