Analyze each of the corresponding algorithms according to the points as follows:
ID: 3878187 • Letter: A
Question
Analyze each of the corresponding algorithms according to the points as follows:
(I). Explain what value you choose for input size n. 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.
(II). If it applies, give your estimates both for the worst case and best case.
(III). 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.
(IV). 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.
NB: give your answers under comments for each method.
Exercises
A.
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:
B.
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
Explanation / Answer
A. Let n be the list length
int find1( int[] list, int element ){
int answer = 0; ---> O(1)
for(int k = 0; k < list.length; k++ )---> n+1
if (element == list[k])---> n
answer++;---> n
return answer;---> O(1)
}//end method
Comments: The best case is O(1), when the element to be found is the first element in list
=> Worst case is O(n) when the element is not in the list , or the element to be found is the last element in the list
----------------------------------------------------------------------------------------------------
B.
public int find2(int[] arr){
//find1 takes O(n) time
int zeroCounter = find1(arr, 0);
if (zeroCounter > arr.length - 2)-> O(1)
return 0;-> O(1)
//Arr.length is n, zeroCounter
while(zeroCounter < arr.length - 2){ --> This will run for n*n time i.e n2
//see maxIndex() definition below
// The maxIndex() takes O(n) time as array length is n
int max = maxIndex(arr);
arr[max] = 0;
//see display() definition below
// The maxIndex() takes O(n) time as array length is n
display(arr);
zeroCounter ++;
}
// The maxIndex() takes O(n) time as array length is n
return maxIndex(arr);
}//end method
//helper methods
// The maxIndex() takes O(n) time as array length is n
int maxIndex(int[]arr){
int maxindex = 0; --> 1
for(int k = 0 ; k< arr.length; k++){ --> n+1
// note the use of absolute value
if(Math.abs(arr[maxindex]) < Math.abs(arr[k])) --> n
maxindex = k;--> n
}
return maxindex;--> 1
}
// The display() takes O(n) time as array length is n
void display(int[]arr){
System.out.println(); --> 1
for(int k = 0 ; k< arr.length; k++) --> n+1
System.out.print(arr[k]+” “);--> n
System.out.println();--> 1
}
Comments: The best case is O(n), when zeroCounter is greater than length-2
=> Worst case is O(n2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.