Consider the following implementation of the algorithm for generating permutations discovered by B$.$ Heap Algorithm HeapPermute$($n$)//$Implements Heaps algorithm for generating permutations$//$Input: A positive integer n and a global array A$[1..$n$]//$Output: All permutations of elements of Aif n $=1$ write Aelse for i $1$ to n do HeapPermute$($n $-1)$ if n is odd swap A$[1]$ and A$[$n$]$ else swap A$[$i$]$ and A$[$n$]1.$ Trace the algorithm by hand for n $=2,3,$ and $4.$ Show your work. Points $52.$ Prove the correctness of Heaps algorithm. Show your work. Points $53.$ What is the time efficiency of HeapPermute?