from A-J inclusively: Perform an experimental analysis of the two algorithms prefixAverage1 and prefixAverage2, from lesson examples. Optionally, visualize their running times as a function of the input size with a log-log chart. Use either Java or Python graphical capabilities for visualization. Hint: Choose representative values of the input size n, similar to StringExperiment.java from class examples.
If your first name starts with a letter from A-J inclusively:
Perform an experimental analysis of the two
Hint: Choose representative values of the input size n, similar to StringExperiment.java from class examples.
class PrefixAverage {
/** Returns an array a such that, for all j, a[j] equals
* the average of x[0], ..., x[j].
* A[j] = (X[0] + X[1] + … + X[j])/(j+1)
*
* ******************************************************/
// inner loop size will be 1, 2, 3, ..., n (based on j=0,1,2,...,n-1)
// we know that 1+2+3+...+ n-1+n = n(n+1)/2
// so, the running time os O(n^2)
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]. */
// the running time is O(n)
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;
}
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 3 images
