Removing outliers from a data set is a key preprocessing step when applying

statistical technqiues in data science. The algorithm REMOVEOUtliers takes as input an

array $A$ of $n$ numbers and a positive number $c$ and outputs a sorted$/$ordered list $L$ of the

numbers in A excluding outliers, where an outlier is defined as a number which deviates more

than a factor $c$ from its average $$ of the numbers in $A,$ relative to the standndard deviation

$$ of the numbers in $A.$ It uses several auxiliary functions. The functions MEAN and STD both

take as input an array of $n$ numbers and output the average and standard deviation of those

numbers, respectively. Assume that they both run in linear time and use a constant amount

of space. The function FINDBETWEEN extracts all the elements of an array $A$ of $n$ numbers

that are larger than a given value $x$ and smaller than another given value $y,$ all given as

input, and returns the elements in A that are in that range using a sorted$/$ordered list data

structure.

Algorithm $3$ REmoveOutLiers $(A,c)$

$larrMEAN(A)$

$larrSTD(A)$

return FINDBETWEEN$(A,-c**,+c**)$

$($a$)$ Provide an efficient algorithm, in pseudcode, for the function FINDBETWEEN 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 $4$ FINDBETWEEn $(A,x,y)$

Llarr new sorted list initially empty

return $L$

a$)$ found above

b$)$ give time and space characterization for removeOutliers and findBetween using big $-$ oh