Java

Perform an experimental analysis of the two algorithms prefixAverage1 and prefixAverage2, from lesson examples. Visualize their running times as a function of the input size with a log-log chart. Use Java graphical capabilities for visualization. Hint: Choose representative values of the input size n, and run at least 5 tests for each size value n.

/** Returns an array a such that, for all j, a[j] equals the average of x[0], ..., x[j]. */ public static double[] prefixAverage1(double[] x) { int n = x.length; double[] a = new double[n]; // filled with zeros by default for (int j=0; j < n; j++) { double total = 0; // begin computing x[0] + ... + x[j] for (int i=0; i <= j; i++) total += x[i]; a[j] = total / (j+1); // record the average } return a; }

/** Returns an array a such that, for all j, a[j] equals the average of x[0], ..., x[j]. */ public static double[] prefixAverage2(double[] x) { int n = x.length; double[] a = new double[n]; // filled with zeros by default double total = 0; // compute prefix sum as x[0] + x[1] + ... for (int j=0; j < n; j++) { total += x[j]; // update prefix sum to include x[j] a[j] = total / (j+1); // compute average based on current sum } return a; }