Question

Java code efficiency: Look at the implementation of the method called intervalSums below. Design and implement a more efficient runtime algorithm for intervalSums. public static long intervalSums(intll A, intl0 B) long count = 0; for (int i = 0; i < A.|ength; i++) { for (int j = i; j < A.length; j++) { int sum = 0; for (int k = i; k <= j; k++) { sum += A[k]; count += 1; B[i][j] = sum; if (j > i) B[j] [i] =-1; // fill the lower "triangle" of B with-1s return count;

Answer 1

Markers □ Properties悦Servers膼Data Source Explorer Snippets Console X Ju JUnit -Coverage terminated> IntervalDemoava Application] CAProgram FilesJava jre1.8.0_12binljavaw.exe (29-0ct-2017, 12:44:19 PM) Count: 81 1 3 6 10 15 21 28 36 45 -1 2 59 14 20 27 35 44 -1 -1 3 7 12 18 25 33 42 -1 -11 4 9 15 22 30 39 -1 -1-1 -1 5 11 18 26 35 -1 -1-1 -1 -1 6 13 21 30

public class IntervalDemo {

   public static long intervalSums(int[] A, int[][] B) {

       long count = 0;
      
       //Overall two loops are required , time complexity will be O(n^2)
       for (int i = 0; i < A.length; i++) {
           for (int j = 0; j < A.length; j++) {
               if (i > j)
                   B[i][j] = -1; // fill the lower "triangle" of B with -1s
               else {
                   //i==j assign i+1
                   if (i == j) {
                       B[i][j] = i + 1;
                   } else {
                       //else case previous element and j and 1
                       B[i][j] = B[i][j - 1] + j + 1;
                   }
               }
               count++;
           }
       }
       return count;
   }

   public static void main(String[] args) {

       int A1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
       int B1[][] = new int[9][9];

       long resultCount = intervalSums(A1, B1);
      
       System.out.println("Count: "+resultCount);

       for (int i = 0; i < 9; i++) {
           for (int j = 0; j < 9; j++) {
               System.out.print(B1[i][j] + " ");
           }
           System.out.println();
       }
   }

}

===============================================
---------------------   
Observations:
---------------------   
   1. Initial code has 3 for loops , This has only 2 for loops
   2. Count value decreased from 165 to 81
   3. This is drastic change in increse in performace.
  
===============================================