the following reduce-and-conquer algorithm was introduced to find the sum of all elements in the array....

 

Transcribed Image Text:

the following reduce-and-conquer algorithm was introduced to find the sum of all elements in the array. With each iteration, the algorithm reduces the number of elements in array by one, and call the function recursively. Modify the algorithm so that, with each iteration, the algorithm reduces the number of elements by 2 elements, provided there are more than 2 elements in the array. To compute the complexity of your algorithm, find the recurrence relationship for the algorithm (using worst case scenario) and solve it using forward or backward substitution. Algorithm LinearRecSum(4, i n): Input: An array A, an int i (starting index for the array) and n (# of elements) Output: The sum of the n integers in A starting at index i if n = 1 then return Ali ] else return A[i]+ LinearRecSum(4, i+1, n-1) the following reduce-and-conquer algorithm was introduced to find the sum of all elements in the array. With each iteration, the algorithm reduces the number of elements in array by one, and call the function recursively. Modify the algorithm so that, with each iteration, the algorithm reduces the number of elements by 2 elements, provided there are more than 2 elements in the array. To compute the complexity of your algorithm, find the recurrence relationship for the algorithm (using worst case scenario) and solve it using forward or backward substitution. Algorithm LinearRecSum(4, i n): Input: An array A, an int i (starting index for the array) and n (# of elements) Output: The sum of the n integers in A starting at index i if n = 1 then return Ali ] else return A[i]+ LinearRecSum(4, i+1, n-1)

Answer rating: 100% (QA)

S olution Algorithm LinearRecSum A i n Input An array A an int i start... View the full answer