4. THE SECOND PART: THE R2 SEARCH ALGORITHM The second setting is now inspired by RAID 2, which stores the "parity" of bits in another piece of hardware. To start this idea, we consider a simple case where, given an array A of non- negative integers of length N, additionally a second single-element array B is created. The array B will store the sum of all the integers in array A, as the following figure demonstrates: A: 75 6 3 2 1 4 8 9 0 1 2 3 4 5 6 7 8 B: 45 @ The idea is that if there is an error in one of the two arrays that changes the values of the integers, the hope is that the value in B will not match the actual sum of all the integers in A. From now on in this assignment we will assume that at most one array might have its values altered, but we do not know which one ahead of time. Task 2: Consider the following pseudocode functions that create such an array B for array A and the integer N, which is the length of the array A: function Sum(A, left, right) if left > right: return else if left = right: return A[left] mid = floor (N/2) lsum = Sum(A, left,mid) rsum = Sum(A, mid+1, right) return lsum + rsum function CreateB(A,N) B = new Array of length 1 B[0] = Sum(A, O, N-1) return B The function CreateB creates this second array using a function call to Sum. For the algorithm CreateB address the following: 1. Explain very briefly in words why the best-case inputs and the worst-case inputs are the same for CreateB. Recall that there are two inputs to CreateB. [6 marks] 2. Use the Master Theorem and to derive the Theta notation for both the worst-case and best-case running times (or execution time) T(N), and show your working and reasoning. [10 marks]