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. 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.
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:(attached image)
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 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 0
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,0,N-1)
return B
The function CreateB creates this second array using a function call to Sum. For the algorithm CreateB address the following:
-
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.
-
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.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
