Question

2 algorithms for Prefix Averages, one that ran in big-Oh n2 time and a
second that ran in big-Oh n time. Code up methods for both algorithms. Show through different
input examples and using the Current Time method call how the polynomial time algorithm runs
slower than the linear time version. Use system.out.println statement to show your results.

please who can help with this question In Java
Thank you

Answer 1

import java.util.Arrays;

import java.util.concurrent.TimeUnit;

public class Main {

public static double[] prefixAverageLinear (double[] arr) { // The algorithm with O(n) time complexity

long startTime = System.nanoTime();

double array[] = new double[arr.length];

double temp = 0;

for (int i = 0; i < arr.length; i++) {

temp += arr[i];

array[i] = temp/(i+1);

System.out.println(Arrays.toString(array));

}

long endTime = System.nanoTime();

long timeTaken = endTime - startTime;

System.out.println("Time taken in milliseconds(Linear): " + timeTaken/1000000);

return array;

}

public static double[] prefixAverageQuadratic (double[] arr) { // The algorithm with O(n^2) time complexity

long startTime = System.nanoTime();

double array[] = new double[arr.length];

for (int i = 0; i < arr.length; i++) {

double temp = 0;

for (int j = 0; j <= i; j++) {

temp += arr[j];

}

array[i] = temp/(i+1);

System.out.println(Arrays.toString(array));

}

long endTime = System.nanoTime();

long timeTaken = endTime - startTime;

System.out.println("Time taken in milliseconds(Quadratic): " + timeTaken/1000000);

return array;

}

public static void main(String[] args){

double array[] = {1,2,3,4,5,6,7,8};

prefixAverageQuadratic(array);

prefixAverageLinear(array);

}

}

Output :

Time for quadratic algo took 6 milliseconds while for linear algo it took 1 milliseconds.

Hence proved linear O(n) algorithm is faster.