Java - Analyze each algorithm according to the points as follows: 1. Choose the

Question

Java -

Analyze each algorithm according to the points as follows:
1. Choose the input size n and explain your choice.
2. In each case T(n) denotes the running time (number of steps) of
the algorithm. Compute T(1) and T(2)
3. Compute and estimate T(n) in terms of the O(n) scale. Use the
simplest and possibly the smallest valid big-Oh expressions.
4. If it applies, point out your estimates both for the worst case and
best case.
5. Document and comment the methods in Exercises 1 – 4. Describe
the tasks of the methods, explain the meaning the return value if
applies, show and justify your big-Oh estimate.
6. It is not necessary to run these methods in actual programs, but if
the task it performs is dubious, testing the method with various
input in actual applications of the code may help to find its
purpose and the big-Oh estimate

1.

int occurrences( int[] list, int element ){
int answer = 0;
for(int k = 0; k < list.length; k++ )
if (element == list[k])
answer++;
return answer;
}//end method
Comments:
2.
public int eliminate(int[] arr){
int zeroCounter = occurrences(arr, 0);
if (zeroCounter > arr.length - 2)
return 0;
while(zeroCounter < arr.length - 2){
//see maxIndex() definition below
arr[maxIndex(arr)] = 0;
//see display() definition below
display(arr);
zeroCounter ++;
}
return zeroCounter;
}//end method

//helper methods
int maxIndex(int[]arr){
int maxindex = 0;
for(int k = 0 ; k< arr.length; k++){
// note the use of absolute value
if(Math.abs(arr[maxindex]) < Math.abs(arr[k]))
maxindex = k;
}
return maxindex;
}
void display(int[]arr){
System.out.println();
for(int k = 0 ; k< arr.length; k++)
System.out.print(arr[k]+” “);
System.out.println();
}
Comments

3.
int maxSubSum(int[] nums){
int answer = nums[0];
int temp = 0;
for(int k = 0; k < nums.length; k++ )
for(int j = k; j< nums.length; j++){
//see helper method subSum below
temp = subSum(nums, k, j );
if (temp > answer)
answer = temp;
}
return answer;
}
Note: Given two indices i<=j of an array of integers num, the sum
num[i]+ num[i+1] + …+ num[j] is called a sub-sum
//helper method
int subSum(int[]arr, int i, int j){
int sum = 0;
for(int k = i; k<= j; k++)
sum += arr[k];
return sum;
}
Comments

4.
void printMany(int[]arr){
int N = arr.length;
for(int k = 0 ; k< N; k++){
int p = k;
while(p>0){
System.out.println(arr[p]+" ");
p = p/2;
}
}
}
Comments

Explanation / Answer

1) int occurrences( int[] list, int element ){
int answer = 0;
for(int k = 0; k < list.length; k++ )
if (element == list[k])
answer++;
return answer;
}//end method

Comments:

1. Let the input size be 8, prefered as it is multiple of prime 2.

2. T(1) = 8; T(2) = 64

3. T(1) = 8; T(2) = n^2

Please do not post multiple questions in the same post. Hope you understand. Thank you

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.