Consider the following algorithm to generate a uniformly random permutation of natural numbers 1, 2, ...n . Start with the sorted array. At each iteration, pick A[1] (that is the first element) and insert it at any of the 11 positions chosen uniformly at random. If it is inserted at A[i], then the index of all numbers from i down to 2 is decremented by 1. Repeat this process till 11 1 becomes the first element and then the above operation is done one final time. o Prove that on termination, the algorithm indeed produces a uniformly random permutation (Hint : Try to prove that at any iteration, ifj is the position of number n 1, then the subarrayA[j,j + 1,- - - n] is a uniformly random permutation of the numbers contained in the subarray. What happens after the final iteration?) o What is the expected number of operations performed by this algorithm (Hint : Use number n 1 as a tracker!)