Hide Assignment Information
Instructions
Running Time: Prefix Averages with JAVA Begin by familiarizing yourself with the idea of a prefix average -- what it is, and how it could be calculated. If you had a list of numbers, and you wanted to have a running total of the cumulative average for each number including all the numbers before it, you could write an algorithm to do that for you in a number of ways. You don't have to actually write that algorithm for this lab, but instead you'll study a couple of different implementations of the algorithm that were given in the text book. Perform an experimental analysis of the algorithms prefixAverage1 and prefixAverage2 from Section 4.3.3. In the main method, implement tests for both of the prefix average algorithms with arrays filled with random values between 0 and 99. Show running time in nano seconds for input size of 10, 100, 1000, 10,000, and 100,000. Output the results, and a print statement with your estimate of running time (constant, logarithmic, linear, n-log-n, quadratic, cubic, or exponential) based on the results of your experiments. Sample output: n = 10 alg1 time: ___ ns. n = 100 alg1 time: ___ ns. n = 1000 alg1 time: ___ ns. n = 10000 alg1 time: ___ ns. n = 100000 alg1 time: ___ ns.* n = 10 alg2 time: ___ ns. n = 100 alg2 time: ___ ns. n = 1000 alg2 time: ___ ns. n = 10000 alg2 time: ___ ns. n = 100000 alg2 time: ___ ns.* These results indicate the growth function of first algorithm is ___, and second algorithm is ___. * (* You fill in the blanks) 4 points - five test of the first algorithm (with n equal to 10, 100, 1000, 10,000, and 100,000), and time in nanoseconds for each. 4 points - five test of the second algorithm (with n equal to 10, 100, 1000, 10,000, and 100,000), and time in nanoseconds for each. 2 points - Your answers for running time of both algorithms. (BIG HINT! Read about both these algorithms in the book!)