Implement pre?x Averages1 and pre?x Averages2 from following codes, and perform

Question

Implement pre?x Averages1 and pre?x Averages2 from following codes, 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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---