Runtime Analysis Analyze each of the corresponding algorithms according to the p
ID: 3878699 • Letter: R
Question
Runtime Analysis
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
C.
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
D.
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
C. Answer :-
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;
}
Worst Case :- In the worst case when outer loop runs for the length of the array means n times and second loop also for each k value at n times (suppose n is length of array) then in this case when we come inside in subsum() function where we are passing the array. So it will also run n times. So in worst case the Big=O time complexity will be O().
Best Case :- In Best case if there is only 1 element in array then O(1) .
D. Answer :-
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;
}
}
Worst Case :- In this function in worst case the for loop will run n times ( as n is length of the array) and inside for loop there is a while loop which takes p>- and p=k where k will be length of the array in the worst case in while it will run only n/2 times only so worst case time complexity for inner while loop will be h. so total time complexity for this will be h log(n).
Best Case :- In best case of array has only 1 element then O(1).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.