The following algorithm is proposed by Bob to find the medium number among all numbers in an integer array. Answer the following questions: (1) Is the algorithm correct? If not which line or lines should be corrected and how? (2) How many operations in terms of size N does this algorithm execute in the worst case and the best case? Show your logic and steps on how to get your answers. Assume each basic operation costs one time unit. a.k.a., A=C=E=1

9. (20 pts) The following algorithm is proposed by Bob to find the medium number among all numbers in an integer array. Answer the following questions: (1) Is the algorithm correct? If not which line or lines should be corrected and how? (2) How many opera- tions in terms of size N does this algorithm execute in the worst case and the best case? Show your logic and steps on how to get your answers. Assume each basic operation costs one time unit. a.k.a., A=C=E=1. Algorithm 1 Find the medium number in an integer array 1: procedure MEDIUM(A[1,2,...,N]) The array is the input 2: //This algorithm returns the medium number among all the numbers in an array. Out- put is the medium number found at position [N/2] after sorted increasingly. 3: i=1 4: for (; i A[j] then m- A[i] A[i] - A[i] A[j- m Swap end if end for 12: end for return A[i] 13: end procedure (bonus 10 pts) Explain why the statement, "The running time of algorithm A is at least O(n)," is meaningless