Java -

Analyze each algorithm according to the points as follows: 1. Choose the input size n and explain your choice. 2. In each case T(n) denotes the running time (number of steps) of the algorithm. Compute T(1) and T(2) 3. Compute and estimate T(n) in terms of the O(n) scale. Use the simplest and possibly the smallest valid big-Oh expressions. 4. If it applies, point out your estimates both for the worst case and best case. 5. Document and comment the methods in Exercises 1 4. Describe the tasks of the methods, explain the meaning the return value if applies, show and justify your big-Oh estimate. 6. 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

1.

int occurrences( 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 eliminate(int[] arr){ int zeroCounter = occurrences(arr, 0); if (zeroCounter > arr.length - 2) return 0; while(zeroCounter < arr.length - 2){ //see maxIndex() definition below arr[maxIndex(arr)] = 0; //see display() definition below display(arr); zeroCounter ++; } return zeroCounter; }//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 maxSubSum(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