Dear Experts, Please provide the solution in Java programming. thanks. 3 questio
ID: 3583889 • Letter: D
Question
Dear Experts,
Please provide the solution in Java programming. thanks.
3 questions as follows. Pls take note the symbol ¬ is actually an arrow pointing to left side.
Exercise: Give a big-Oh characterization for below questions.
1.
Algorithm Ex1(A, n)
Input an array X of n integers
Output the sum of the elements in A
s ¬ A[0]
for i ¬ 0 to n - 1 do
s ¬ s + A[i]
return s
2.
Algorithm Ex2(A, n)
Input an array X of n integers
Output the sum of the elements at even cells in A
s ¬ A[0]
for i ¬ 2 to n - 1 by increments of 2 do
s ¬ s + A[i]
return s
3.
Algorithm Ex1(A, n)
Input an array X of n integers
Output the sum of the prefix sums A
s ¬ 0
for i ¬ 0 to n - 1 do
s ¬ s + A[0]
for j¬ 1 to i do
s ¬ s + A[j]
return s
Explanation / Answer
Please find the answers below along with the comments, which explains each step :
1)
Algorithm Ex1(A, n)
double Ex1(int[] A, int n) {
double s = A[0]; //initialize sum variable s with first element in array A
for(int i=1; i<= n-1; i++){ //iteration to find sum of all elements in the array A
s = s + A[i]; //add the value at position i
}
return s; //return s;
}
Here O(n) will be equal to the no:of loop iterations because the rest of the statements in the function are O(1) which are constant. Thus O(n) = n.
2)
Algorithm Ex2(A, n)
double Ex2(int[] A, int n) {
double s = A[0]; //initialize sum variable s with first element in array A
for(int i=2; i<= n-1; i=i+2){ //iteration to find sum of all elements in the array A, in which the iteration variable i will contains even values 2,4,6,...n-1 (note that i increments by 2)
s = s + A[i]; //add the value at position i (which will be an even position)
}
return s; //return s;
}
Here O(n) will be equal to the no:of loop iterations because the rest of the statements in the function are O(1) which are constant. Thus O(n) = n/2. Because here the iteration steps by 2.
3)
Algorithm Ex3(A, n)
double Ex3(int[] A, int n) {
double s = 0; //initialize sum variable s as 0
for(int i=0; i<= n-1; i=i+2){ //outer iteration loop
s = s + A[0]; //add the value at position i
for(int j=1; i<= i; i=i+2){ //inner iteration loop
s = s + A[i]; //summation
}
}
return s; //return s;
}
Here O(n) will be equal to the no:of loop iterations because the rest of the statements in the function are O(1) which are constant. Thus O(n) = n x n = n2. Because here there is an inner loop within an outer, thus in an average case it will be n x n.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.