How to answer this question according to the mark ?

An algorithm teacher has been inventing a lot of increasingly crazier algorithms lately, just so his students cannot find answers about them on the Internet. The following is one of his less crazy inventions, which purportedly sorts an array: (a) Demonstrate the execution of this algorithm with an input array A formed by last 5 digits of your university number. For example, if your university number is 229054321 , then A=[5,4,3,2,1]. You should show the contents of the array each time the NewSort() function is about to end, and the values of i and j at those times. [5 marks] (b) Write down a recurrence expressing the time complexity of this algorithm. [5 marks] (c) Solve the recurrence in (b). You must not use the Master Theorem, but it is enough to give the answer in big-O. [20 marks] 1