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

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

int total= 0;

for (int j=0; j

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.