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