question ex 2.

Exercise 2. Consider the following algorithm ALGO-X(A) that takes an arrays A of numbers, pos- sibly negative, sorted in non-decreasing order. ALGO-X(A) 1 B = empty array 2n = A. length 3 for i = 1 ton 4 append value (A[i])2 to B 5 for i = 2 ton j =i-1 7 V = B[i] 8 while j> 0 and B[] > v 9 B[j+1] - BU 10 j = j-1 11 B[i+1] = v 12 return B Answer the following questions in a PDF document called ex2.pdf: 6 Question 1: Explain what ALGO-X does. Do not simply paraphrase the code. Instead, explain the (10) high level semantics, independent of the code. Question 2: Analyze the complexity of ALGO-X in the best and worst case. Justify your answer by (10) clearly describing a best and worst-case input of size n, as well as the behavior of the algorithm in each case. Question 3: Write an algorithm called BETTER-ALGO-X that does exactly the same thing as ALGO-X (20) in O(n) time. Analyze the complexity of BETTER-ALGO-X