Design & Analysis of Algorithms

*I understand these answers may be long, so I would be fine with help on just b and c (but you can still help on all parts if you would like)

1. Consider the following algorithm. Procedure 1: MYSTERY (A, n) Input: A positive integer n and an array All..1n where m n output: It's a mystery! 1 if n 1 then 2 print A 3 else 4 for i 1 to n do MYSTERY(A,n-1) if n is odd then swap All] and Aln else I swap Ali] and Aln] (a) Assume that the glob array All..9) (a, i,g, o, r, i, t, h,m). Trace the algorithm for n 2 and n 3 (b) What does the MYSTERY algorithm compute? Justify your answer. (c) Write a recurrence relation describing the running time of the algorithm. That is, setup a recurrence relation for the number of swaps made by the algorithm. (d) Solve the recurrence you wrote in part (c) using repeated substitution