I Question 1 Consider the following algorithm Algorithm 1: Mystery A.n) Input : Array A of n numbers on-1 with 21 Output: See question (a) below 1 if n1 then 2 Print the message "Mystery solved" 3 else +1: while sn-1 do 6 if a-1 > a, then swap a; - 1 and 1+1+1; Mystery(A.n-1); 5 1 (a) Using A = (9.5,11.3.2) as the input array, hand-trace Mystery, showing the values of ij. and the array elements just before line 8 is executed (b) Determine the running time 7') as a function of the number of comparisons made on line 6, and then indicate its time and space efficiency (ie. O and I bounds) (c) Determine the running time 7(n) as a function of the number of swaps made on line 7 and indicate its time and space efficiency (d) Suggest an improvement, or a better algorithm altogether, and indicate its time and space efficiency. If you cannot do it, explain why it cannot be done? (e) Can Mystery be converted into an iterative algorithm? If it cannot be done, explain why: otherwise, do it and determine its running time complexity in terms of the number of comparisons of the array elements. I Question 1 Consider the following algorithm Algorithm 1: Mystery A.n) Input : Array A of n numbers on-1 with 21 Output: See question (a) below 1 if n1 then 2 Print the message "Mystery solved" 3 else +1: while sn-1 do 6 if a-1 > a, then swap a; - 1 and 1+1+1; Mystery(A.n-1); 5 1 (a) Using A = (9.5,11.3.2) as the input array, hand-trace Mystery, showing the values of ij. and the array elements just before line 8 is executed (b) Determine the running time 7') as a function of the number of comparisons made on line 6, and then indicate its time and space efficiency (ie. O and I bounds) (c) Determine the running time 7(n) as a function of the number of swaps made on line 7 and indicate its time and space efficiency (d) Suggest an improvement, or a better algorithm altogether, and indicate its time and space efficiency. If you cannot do it, explain why it cannot be done? (e) Can Mystery be converted into an iterative algorithm? If it cannot be done, explain why: otherwise, do it and determine its running time complexity in terms of the number of comparisons of the array elements