8. R-4.8 Order the following functions by asymptotic growth rate. 4nlogn + 2n 2^
ID: 3719871 • Letter: 8
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.
Explanation / Answer
As per Chegg 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).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.