Implement pre?x Averages1 and pre?x Averages2 from following algorithms , and pe
ID: 3649072 • Letter: I
Question
Implement pre?x Averages1 and pre?x Averages2 from following algorithms , and perform an experimental analysis of their running times. Visualize their running times as a function of the input size with a log-log chart.Algorithm
pre?xAverages1 ( X ):
Input:
An n-element array X of numbers.
Output:
An n-element array A of numbers such that A[i] is the average of elements X [0],..., X [i]. Let A be an array of n numbers.
for i?0 to n?1 do
a?0
for j?0 to i do
a?a+ X [ j]
A[i]?a/(i+1)
return array A
Algorithm
pre?xAverages2( X ):
Input:
An n-element array X of numbers.
Output:
An n-element array A of numbers such that A[i] is the average of elements X [0],..., X [i].
Let A be an array of n numbers.
s?0
for i?0 to n?1 do
s?s+ X [i]
A[i]?s/(i+1)
return array A
Explanation / Answer
Algorithm prefixAverages1(X): Input: An n-element array X of numbers. Output: An n -element array A of numbers such that A[i] is the average of elements X[0], ... , X[i]. Let A be an array of n numbers. for i? 0 to n - 1 do a?0 for j ? 0 to i do Analyze a ? a + X[j] A[i] ? a/(i+ 1) return array A this has complexity O(n^2) whereas Algorithm prefixAverages2(X): Input: An n-element array X of numbers. Output: An n -element array A of numbers such that A [i] is the average of elements X[0], ... , X[i]. Let A be an array of n numbers. s? 0 for i ? 0 to n do s ? s + X[i] A[i] ? s/(i+ 1) return array A Has the complexity O(n) So you should choose 2nd algorithm over 1 st