Consider a problem of computing the prefix average of a sequence of numbers stored in an array X consisting of n integers. We want to compute an array A such that A[i]is the average of X[0],X[1],…,X[i] for i=0,1,….,n-1.
Consider the two algorithms related to the above problem. Answer the questions given below.
a- Determine the worst runtime complexity of both the algorithms.
b- Comment which algorithm is better than the other?
Answers
Answered by
0
Answer:Given an array arr[] of size n, its prefix sum array is another array prefixSum[] of same size such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] … arr[i].
Examples :
Input : arr[] = {10, 20, 10, 5, 15}
Output : prefixSum[] = {10, 30, 40, 45, 60}
Explanation : While traversing the array, update
the element by adding it with its previous element.
prefixSum[0] = 10,
prefixSum[1] = prefixSum[0] + arr[1] = 30,
prefixSum[2] = prefixSum[1] + arr[2] = 40 and so on.
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.
To fill prefix sum array, we run through index 1 to last and keep on adding present element with previous value in prefix sum array.
Explanation:
Similar questions