$[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 a 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 pseudeode, 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$,,$ y$)$

$1$: L $+$ new sorted list initially empty

$2$:

$5$: 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.

Time

Space