Algorithm Analysis 1) The number of operation executed by algorithm A and B is 8
ID: 3870850 • Letter: A
Question
Algorithm Analysis
1) The number of operation executed by algorithm A and B is 8n log n and 2n2 respectively. Determine n0 such that A runs faster than B for n great than equal to n0.
2) What is the running time characterization of example1 in terms of input size n?
public static int example1(int[] arr){
int total =0;
for(int i=0; i < arr.length; i++)
total += arr[i];
return total;
}
3) What is the running time characterization of example2 in terms of input size n?
public static int example2(int[] arr){
int total =0;
for(int i=0; i < arr.length; i+=2)
total += arr[i];
return total;
}
4) What is the running time characterization of example3 in terms of input size n?
public static int example3(int[] arr){
int total =0;
for(int i=0; i < arr.length; i++)
for(int j = 0; j <=i; j++)
total += arr[i];
return total;
}
5) What is the running time characterization of example4 in terms of input size n?
public static int example4(int[] arr){
int total = 0, prefix = 0;
for(int i=0; i < arr.length; i++){
prefix += arr[i];
total += prefix;
}
return total;
}
6) What is the running time characterization of example5 in terms of input size n?
public static int example5(int[] first, int[] second){
int count = 0, total = 0;
for(int i=0; i < first.length; i++){
total = 0;
for(int j=0; j < first.length; j++)
for(int k=0; k <= j; k++)
total += first[k];
if(second[i]==total) count++;
}
return count;
}
Explanation / Answer
1)
Algorithm A’s complexity is 8*n*log(n)
Algorithm B’s complexity is 2*n2
We know that nlog(n) < n^2
Therefore algorithm A will run faster than algorithm B.
2)
The function example1 will take an array of size “n” as parameter.
The for loop will start from 0 to length of the array, which is n. therefor it will iterate n times, for every iteration, it will add array[i] to “total” variable.
Total += arr[j] will take constant time.
So, the time complexity is O(n).
3)
The function example2 will take an array of size “n” as parameter.
The for loop starts from 0 to length of the array with i=i+2 increment.
So,
I = 0 2 4 6 8 10 . . . n
n/2 times for loop will iterate.
So the time complexity is O(n/2)
Which is O(n).
4)
The function example3 will take an array of size “n” as parameter.
The outer for loop will start from 0 to n.
The inner loop start from 0 to outer for loop’s index number.
The inner statement takes constant time.
I = 0 1 2 3 4 . . . n
J = 0 0,1 0,1,2 0,1,2,3 . . . . 0,1,2,3….n
Therefore, the time complexity is O(n2)
5)
The function example4 will take an array of size “n” as parameter.
The for loop start from 0 to n.
The inner 2 statements will take constant time.
So, the time complexity is O(n).
6)
This method will take 2 parameters, one is first[] array and another one is second[] array.
The outer loop will start from 0 to first[] array’s length. Lets take it as n.
So n times.
The inner loop will also start from j=0 to first[] array’s length.
This is also take n times.
Till now it is n*n times.
The innermost array also take n times.
So, the overall time complexity is O(n3 )
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.