Question

Calculating prefix average of a set of values is an important problem, especially in financial calculations. Use the following link to understand background on prefix averages problem - http://csfundamentals.com/tech-interview/dsa/prefix-averages-algorithm-java-program.php Consider the algorithms (methods) – prefixAverage1 and prefixAverage2 for calculating prefix averages. The source code is given to you. Implement both the algorithms and perform an experiment analysis of their running times under different input sizes. Visualize the running times on a chart, where x-axis represents different input sizes and y-axis represents running times of the algorithms.

Code:

package Assignment2;

/**
* Demonstration of algorithms for computing the prefix averages of an array.
*
* @author Michael T. Goodrich
* @author Roberto Tamassia
* @author Michael H. Goldwasser
*/
class PrefixAverage {

/** 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;
}

}

Answer 1

public class PrefixAverage {
        /**
         * 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;
        }
        
        public static double[] createRandomArray(int size) {
                double result[] = new double[size];
                
                for(int i=0; i<size; i++) {
                        result[i] = Math.random() * size;
                }
                
                return result;
        }
        
        public static void findTime(int size) {
                System.out.println("For Size: " + size);
                double data[] = createRandomArray(size);
                
                long start = System.currentTimeMillis();
                prefixAverage1(data);
                long end = System.currentTimeMillis();
                System.out.println("Prefix1 time: " + (end - start) + " ms");
                
                start = System.currentTimeMillis();
                prefixAverage2(data);
                end = System.currentTimeMillis();
                System.out.println("Prefix2 time: " + (end - start) + " ms\n");
        }
        
        public static void main(String args[]) {
                findTime(100);
                findTime(1000);
                findTime(10000);
                findTime(100000);
        }
}

**************************************************
The prefix1 Algorithm is an O(N^2) algorithm, Since it has nested loops.. in each iteration, it starts from First element and goes till ith Element, Due to which it is an O(N^2) algorithm
The Prefix2 algorithm is a linear O(N) algorithm, as it uses just one loop. It rebuilds the result by adding more data on previous calculation, hence it is optimized.


Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.