Zookal Homework Help

Homework Help

  1. Engineering
  2. Computer Science
  3. need help with this homework question in java...

Question: need help with this homework question in java...

Question details

Need help with this homework question in JAVA.
1. Perform an experimental analysis of the two algorithms prefixAverage1 and prefixAverage2. Visualize their running times as a function of the input size witha chart. Hint: You need to pick several input sizes (say N=500, 1000, 2000, 4000, 8000) and run at least 5 tests on each input size (randomly generated array each time) to have an accurate estimate on the running time. Focus tes)

Prefix Averages (Quadratic) The following algorithm computes prefix averages in quadratic time by applying the definition Algorithm prefixAvgl (X): input: An n-element array X output: An n-element array A of numbers such that A[i] is the average of elements X[0], ..., X[i] 1 Declare and initialize array A 2 for i- 0 to n-1 do a=0 for j = 0 to i do 4 a += X[j] 7 return array A

Prefix Averages 2 (Linear) The following algorithm uses a running summation to improve the efficiency Algorithm prefixAvg2 (X): input: An n-element array X output: An n-element array A of numbers such that A [i] is the average of elements X[0], ..., X[i] 1 Declare and initialize array iA 3for i = 0 to n-1 do a += X[1] 6 return array A Algorithm prefixAverage2 runs in O(n) time!

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution