Question

8.         R-4.8 Order the following functions by asymptotic growth rate.

4nlogn + 2n 2^10    2^logn

3n + 100logn      4n     2^n

n^2 + 10n        n^3       nlogn

9.         R-4.9 Give a big-Oh characterization, in terms of n, of the running time of the example 1 method shown in Code Fragment 4.12.

10.       R-4.10 Give a big-Oh characterization, in terms of n, of the running time of the example 2 method shown in Code Fragment 4.12.

11.       R-4.11 Give a big-Oh characterization, in terms of n, of the running time of the example 3 method shown in Code Fragment 4.12.

12.       R-4.12 Give a big-Oh characterization, in terms of n, of the running time of the example 4 method shown in Code Fragment 4.12.

13.       R-4.13 Give a big-Oh characterization, in terms of n, of the running time of the example 5 method shown in Code Fragment 4.12.

/?? 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++)

total += arr[j];

return total;                   // loop from 0 to n-1

/?? 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)

total += arr[j];

return total;                       // note the increment of 2

}

/** Returns the sum of the prefix sums of given array. */
public static int example3 (int [] arr) {

int n = arr.lenght, 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.lenght, prefix = 0, total = 0;
for int j= 0; j < n ; j++){              //loop from 0 to n-1

prefix += arr[j];

total += prefix;
}
return total;
}

/**returns the number of times second array stores sum of prefix sums from first*/

public static int example5(int[] first, int[] second){     //assume equal length arrays

int n = first.lenght, count=0;

for (int i=0; i<n; i++){    //loop from 0 to n-1

int 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 +=first[k];

if (second[i] == total) count++;

}

return count;

}

Code Fragment 4.12: Some sample algorithms for analysis.

Answer 1

As per HOMEWORKLIB POLICY, I am answering only 4 questions. In order to get the solution of remaining questions, please upload them again.

9.) since j runs from 0 to n-1. Therefore, its running time is O(n).

10.) since j runs from 0 to n-1 but with increment of 2. So, it will run for n/2 times which is O(n).

11.) Inner for loop runs as

1 + 2 + 3+ ... + n-1 = n*(n+1)/2 which is O(n^2).

12.) since j runs from 0 to n-1. Therefore, its running time is O(n).

13.) since i runs from 0 to n-1. Therefore, its running time is O(n).

nner for loop runs as

1 + 2 + 3+ ... + n-1 = n*(n+1)/2 which is O(n^2).

Now, O(n) + O(n^2) = O(n^2).