- In the exercises below there is given a code for methods named find1, find2, f
ID: 3889135 • Letter: #
Question
- In the exercises below there is given a code for methods named find1, find2, find3 and printMany. Analyze each of the corresponding algorithms according to the points as follows:
1. Choose the input size n and explain your choice. Estimate the running time (number of steps) T(n) in terms of the O(n) scale. Use the simplest and possibly the smallest valid big-Oh expressions.
2. If it applies, point out your estimates both for the worst case and best case.
3. Document and comment each method. Describe the tasks of the methods, explain the meaning the return value if applies, show and justify your big-Oh estimate.
4. 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.
Exercises
1.
int find1( 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 find2(int[] arr){
int zeroCounter = find1(arr, 0);
if (zeroCounter > arr.length - 2)
return 0;
while(zeroCounter < arr.length - 2){
//see maxIndex() definition below
int max = maxIndex(arr);
arr[max] = 0;
//see display() definition below
display(arr);
zeroCounter ++;
}
return maxIndex(arr);
}//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 find(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
int find1( 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:
The complexity here will be O(n) where n is the size of the list.
Here it is finding the element in the list so it has to traverse through all the elemens in the list.
The best case will be that the element is found in the first position that is O(1) and the worst case is that element is found in nth position that is O(n).
Hence the avg complexity is O(n/2)=O(n)
2.
public int find2(int[] arr){
int zeroCounter = find1(arr, 0);
if (zeroCounter > arr.length - 2)
return 0;
while(zeroCounter < arr.length - 2){
//see maxIndex() definition below
int max = maxIndex(arr);
arr[max] = 0;
//see display() definition below
display(arr);
zeroCounter ++;
}
return maxIndex(arr);
}//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 :
the complexity for this one is O(n^2) as there is loop while loop from which it is calling function display which also has a for loop in it.
Hence it is basically a loop inside a loop .Hence its complexity will be O(n^2)
3.
int find(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
the complexity for this one is O(n^2) as there is loop for loop from which it is calling function for sum which also has a for loop in it.
Hence it is basically a loop inside a loop .Hence its complexity will be O(n^2)
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
the complexity for this one is O(n^2) as there is loop for loop ,inside it is also a loop while which will execute p times.
Hence it is basically a loop inside a loop .Hence its complexity will be O(n^2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.