Problem 5. Merge-Sort Array Space. Consider the pseudocode for MERGE and MERGE-SORT in Section 2.3. We suppose that the array A is passed by reference", so there is only one copy of A. Note that MERGE allocates two new arrays, Land R. We'll suppose that a new array of size k uses k+1 words of memory. 5(a). Let A(n) be the total number of words of memory used for all of the new arrays allocated during MERGE-SORT, on an input array of size n. Give a estimate for A(n), and briefly justify your answer (a couple of sentences may suffice). Note we are not "recycling" memory yet (that's the next part). 5(b). Now we suppose that the allocated arrays are recycled back to the system when MERGE is done with them. (The memory for Land Ris returned to the system at the end of MERGE, so that the memory can be reused). Let S(n) be the total number of words of memory that we need, in order to allocate all the arrays used during MERGE-SORT, on an input array of size n, assuming the memory is reused as much as possible. Again give a estimate for the S(n), and justify your answer (again, a sentence or two may suffice). Remark: besides the arrays, MERGE-SORT needs an additional O(lg n) words of stack space to keep track of all the recursive calls, but I'm not asking you about that. Problem 5. Merge-Sort Array Space. Consider the pseudocode for MERGE and MERGE-SORT in Section 2.3. We suppose that the array A is passed by reference", so there is only one copy of A. Note that MERGE allocates two new arrays, Land R. We'll suppose that a new array of size k uses k+1 words of memory. 5(a). Let A(n) be the total number of words of memory used for all of the new arrays allocated during MERGE-SORT, on an input array of size n. Give a estimate for A(n), and briefly justify your answer (a couple of sentences may suffice). Note we are not "recycling" memory yet (that's the next part). 5(b). Now we suppose that the allocated arrays are recycled back to the system when MERGE is done with them. (The memory for Land Ris returned to the system at the end of MERGE, so that the memory can be reused). Let S(n) be the total number of words of memory that we need, in order to allocate all the arrays used during MERGE-SORT, on an input array of size n, assuming the memory is reused as much as possible. Again give a estimate for the S(n), and justify your answer (again, a sentence or two may suffice). Remark: besides the arrays, MERGE-SORT needs an additional O(lg n) words of stack space to keep track of all the recursive calls, but I'm not asking you about that