Question

Algorithm1 prefixAverages1(X, n)

Input array X of n integers

Output array A of prefix averages of X

A ← new array of n integers

for i ← 0 to n − 1 do

s ← X[0]

for j ← 1 to i do

s ← s + X[j]

A[i] ← s / (i + 1)

return A

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Algorithm2 prefixAverages2(X, n)

Input array X of n integers

Output array A of prefix averages of X

A ← new array of n integers

s ← 0

for i ← 0 to n − 1 do

s ← s + X[i]

A[i] ← s / (i + 1)

return A

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.

programming language: java

Answer 1

Explanation:I have written both the methods prefixAverages1() and prefixAverages2() and have also shown the output by using the main method, please find the image attached with the answer.It is evident by seeing the start and end time of both algorithms that polynomial takes more time than linear.Please upvote if you liked my answer and comment if you need any modification or explanation.

//code

import java.util.Random;

public class PrefixAverages {

   public static int[] prefixAverages1(int x[], int n) {
       int a[] = new int[n];
       for (int i = 0; i < n; i++) {
           int s = a[0];
           for (int j = 1; j < i; j++) {
               s += a[j];
               a[i] = s / (i + 1);
           }
       }
       return a;
   }
   public static int[] prefixAverages2(int x[], int n) {
       int a[] = new int[n];
       int s = 0;
       for (int i = 0; i < n; i++) {
           s = s + x[i];
           a[i] = s / (i + 1);
       }
       return a;
   }

   public static void main(String[] args) {
       int x[] = new int[1000];
       Random random = new Random();
       for (int i = 0; i < x.length; i++) {
           x[i] = random.nextInt(100);
       }
       System.out.println("For n=1000:");
       System.out.println("Time for polynomial time algorithm:");
       System.out.println("Start time: " + System.currentTimeMillis());
       int a[] = prefixAverages1(x, x.length);
       System.out.println("End time: " + System.currentTimeMillis());
       System.out.println("Time for linear time algorithm:");
       System.out.println("Start time: " + System.currentTimeMillis());
       a = prefixAverages2(x, x.length);
       System.out.println("End time: " + System.currentTimeMillis());
       System.out.println();
       x = new int[10000];
       for (int i = 0; i < x.length; i++) {
           x[i] = random.nextInt(100);
       }
       System.out.println("For n=10000:");
       System.out.println("Time for polynomial time algorithm:");
       System.out.println("Start time: " + System.currentTimeMillis());
       a = prefixAverages1(x, x.length);
       System.out.println("End time: " + System.currentTimeMillis());

       System.out.println("Time for linear time algorithm:");
       System.out.println("Start time: " + System.currentTimeMillis());
       a = prefixAverages2(x, x.length);
       System.out.println("End time: " + System.currentTimeMillis());

   }

}

Output: