c only

4. [15 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. The algorithm GETOUTLIERS 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 containing only 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 standard 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 FINDOUTSIDE extract 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. (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 sortedlist 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 inclicate the proper scope of each statement.) Algorithm 4 FINDOUTSIDE (A,x,y) 1: L new sorted list initially empty 2: 3: 4: 5: return L (b) Give the tightest/best possible time and space characterization, Big-Oh and Big-Omega, or simply Big-Theta, 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 anount of space. c) Give the tightest/best possible time and space characterization, Big-Oh and Big-Omega, or simply Big-Theta, in terms of n, of algorithm GETOUTLIERS. Justify your