Question

Perform an experimental analysis to test and compares the relative running times of the methods shown in the following Code Fragments. Calculate the execution time of each example in milliseconds and draw the results in one chart using line chart type. [HINT: use the following five different inputs size to check each example (1000, 10000, 100000, 1000000, 10000000). You can generate each array using random number generator to fill the array with the pervious input size].

/** Returns the sum of the integers in given array. */ public static int example1(int[] arr) { int n = arr.length, total = 0; for (int j=0; j < n; j++) // loop from 0 to n-1 total += arr[j]; return total; } /** Returns the sum of the integers with even index in given array. */ public static int example2(int[] arr) { int n = arr.length, total = 0; for (int j=0; j < n; j += 2) // note the increment of 2 total += arr[j]; return total; } /** Returns the sum of the prefix sums of given array. */ public static int example3(int[] arr) { int n = arr.length, total = 0; for (int j=0; j < n; j++) // loop from 0 to n-1 for (int k=0; k <= j; k++) // loop from 0 to j total += arr[j]; return total; } /** Returns the sum of the prefix sums of given array. */ public static int example4(int[] arr) { int n = arr.length, prefix = 0, total = 0; for (int j=0; j < n; j++) { // loop from 0 to n-1 prefix += arr[j]; total += prefix; } return total; } }

Answer 1

Input array size on x axis and execution time on y axis.

Code used for the testing:

package test;

public class Experiment {
   public static void main(String[] args){
       int[] arr;
       long time_start;
       long time_end;
       int arr_size = 100;
      
       for(int i = 0; i < 5; i++){
           /*
           * calculating array size for current run
           */
           arr_size *= 10;
           /*
           * getting array of andom numbers for current run
           */
           arr = getRandomArray(arr_size);
          
           System.out.println("First round run with array size: " + arr_size);          
           System.out.println("\tRunning function example1: ");
           /*
           * getting current system time before execution
           */
           time_start = System.currentTimeMillis();
           System.out.println("\t\tStarting time: " + time_start);
           /*
           * execution of example1 function
           */
           Experiment.example1(arr);
           /*
           * getting current system time after execution
           */
           time_end = System.currentTimeMillis();
           System.out.println("\t\tEnding time: " + time_end);
           System.out.println("\t\tExecution time: " + (time_end - time_start));
                  
          
          
           System.out.println("\tRunning function example2: ");
           /*
           * getting current system time before execution
           */
           time_start = System.currentTimeMillis();
           System.out.println("\t\tStarting time: " + time_start);
           /*
           * execution of example2 function
           */
           Experiment.example2(arr);
           /*
           * getting current system time after execution
           */
           time_end = System.currentTimeMillis();
           System.out.println("\t\tEnding time: " + time_end);
           System.out.println("\t\tExecution time: " + (time_end - time_start));
          
          
          
           System.out.println("\tRunning function example3: ");
           /*
           * getting current system time before execution
           */
           time_start = System.currentTimeMillis();
           System.out.println("\t\tStarting time: " + time_start);
           /*
           * execution of example3 function
           */
           Experiment.example3(arr);
           /*
           * getting current system time after execution
           */
           time_end = System.currentTimeMillis();
           System.out.println("\t\tEnding time: " + time_end);
           System.out.println("\t\tExecution time: " + (time_end - time_start));
          
          
          
           System.out.println("\tRunning function example4: ");
           /*
           * getting current system time before execution
           */
           time_start = System.currentTimeMillis();
           System.out.println("\t\tStarting time: " + time_start);
           /*
           * execution of example4 function
           */
           Experiment.example4(arr);
           /*
           * getting current system time after execution
           */
           time_end = System.currentTimeMillis();
           System.out.println("\t\tEnding time: " + time_end);
           System.out.println("\t\tExecution time: " + (time_end - time_start));
  
       }
   }
  
   public static int[] getRandomArray(int length){
       int[] arr = new int[length];
       for(int i = 0; i < length; i++){
           arr[i] = (int) Math.random() * 100;
       }
       return arr;
   }
  
   /** Returns the sum of the integers in given array. */
   public static int example1(int[] arr) {
       int n = arr.length, total = 0;
       for (int j=0; j < n; j++) // loop from 0 to n-1
           total += arr[j]; return total;
   }
  
   /** Returns the sum of the integers with even index in given array. */
   public static int example2(int[] arr) {
       int n = arr.length, total = 0;
       for (int j=0; j < n; j += 2) // note the increment of 2
           total += arr[j];
       return total;
   }
  
   /** Returns the sum of the prefix sums of given array. */
   public static int example3(int[] arr) {
       int n = arr.length, total = 0;
       for (int j=0; j < n; j++) {// loop from 0 to n-1
           for (int k=0; k <= j; k++) // loop from 0 to j
               total += arr[j];
       }
       return total;
   }
  
   /** Returns the sum of the prefix sums of given array. */
   public static int example4(int[] arr) {
       int n = arr.length, prefix = 0, total = 0;
       for (int j=0; j < n; j++) { // loop from 0 to n-1
           prefix += arr[j];
           total += prefix;
       }
       return total;
   }
}

Code screenshot:

Output of execution: