4. Consider the following implementation of the algorithm for generating permutations discovered by B. Heap [Hea63]. ALGORITHM HeapPermute(n) l/Implements Heap's algorithm for generating permutations llnput: A positive integer n and a global array Al[1.n] //Output: All permutations of elements of A if n 1 write A else for i -1 to n do HeapPermutein -1) if n is odd swap A[1] and Aln] else swap A1 and An] a. Trace the algorithm by hand for n 2, 3, and 4. b. Prove e. What is the time efficiency of HeapPermute? the correctness of Heap's algorithm