In the exercises below there is given a code for methods named find1, find2, fin
ID: 3588591 • Letter: I
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
1.
int find1( int[] list, int element ){
int answer = 0;
for(int k = 0; k < list.length; k++ ) ==> This line runs for n+1 time i.e if the list length is n. +1 because when k becomes list length then condition fails
if (element == list[k]) ===> This line runs for n times
answer++;
return answer; }//end method==> Runs once
Comments:
The overall Since the method runs for n+1 + n + 1 = . 2n+ 1 => O(n). The overall time complexity is O(n)
2.
public int find2(int[] arr){
int zeroCounter = find1(arr, 0);==> Runs for O(n) time as computed above
if (zeroCounter > arr.length - 2)==> Runs for only once
return 0;
while(zeroCounter < arr.length - 2){ . => Runs for arr.lenth ie. n time
//see maxIndex() definition below
int max = maxIndex(arr);=> Runs for O(n) time itself and n time because of upper while loop so its O(n*n) = O(n2)
arr[max] = 0;
//see display() definition below
display(arr);==> Runs for O(n) time itself and n time because of upper while loop so its O(n*n) = O(n2)
zeroCounter ++;
}
return maxIndex(arr);
}//end method
//helper methods int maxIndex(int[]arr){ int maxindex = 0;
for(int k = 0 ; k< arr.length; k++){ ===> Runs for n +1 time
// note the use of absolute value if(Math.abs(arr[maxindex]) < Math.abs(arr[k]))==> Runs for n time
maxindex = k;
}
return maxindex;=> Runs only once
}
Overall time complexity for maxIndex is O(n)
void display(int[]arr){
System.out.println();
for(int k = 0 ; k< arr.length; k++) > Runs for n +1 time
System.out.print(arr[k]+” “);> Runs for n time
System.out.println(); Runs only once
}
Overall time complexity for display is O(n)
Comments :
Overall time complexity for find2 is O(n2)
3.
int find(int[] nums){
int answer = nums[0];
int temp = 0;
for(int k = 0; k < nums.length; k++ ) ===>Runs for n +1 time
for(int j = k; j< nums.length; j++){==>Runs for n time itself and n time because of outer loop so its O(n2)
//see helper method subSum below
temp = subSum(nums, k, j );==>Runs for n time itself as calculated below and n2 because of outer loop so its O(n3)
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]; ==> Maximum runs for n time when i =0 and j is n
return sum;
}
Comments:
Overall time complexity for find is O(n3)
4.
void printMany(int[]arr){
int N = arr.length; ==> Runs once
for(int k = 0 ; k< N; k++){ ==> Runs for N time
int p = k;
while(p>0){ ==> Runs for log2 n time see how
System.out.println(arr[p]+" ");
p = p/2;
}
}
}
Comments:
While loop runs depends on how p is reducing lets take p = 8 , while loop will run for 8, 4, 2 i.e log2 8 = 3 times
Take p = 16, while loop will run for 16, 8, 4, 2 i.e log2 16 = 4 times. so OVERALL time complexity is N*log n = n log n
=> O(n log n)