Java

Part 4: Algorithm Analysis 1. Given the following algorithms below, give a f(n) such that R(n) O(f(n)) where R(n) is the running time for input of size n. For each problem, you must provide justification. Proper justification must include i) a written explanation and ii) a diagram and/or mathematical reasoning. a. R(n) is the running time of something(n), in terms of the argument n.

public static int something(int n){ for (int i=1; i

public static void printItB(int n){ for(int i = 0; i < n; i++) { for(int j = n; j > 0; j/=2) { System.out.println("Something"); } } } c. R(n) is the running time of strange_sumA in terms of n, the length of arr.

int strange_sumA(int[] arr) { if (arr.length == 1) { return arr[0]; } else { int newlen = arr.length/2; int[] arrLeft = new int[newlen]; int[] arrRight = new int[newlen]; for (int i=0; i

d. R(n) is the running time of strange_sumB in terms of n, the length of arr. (If it makes the analysis easier, you may assume that the length of arr is a power of 2).

int strange_sumB(int[] arr, int left, int right) { if (right - left == 1) { return arr[left]; } else { return strange_sumB(arr, left, right/2) + strange_sumB(arr, right/2, right); } }

e. strangeSumA and strangeSumB both sum the elements of an array. Why do strangeSumA and strangeSumB have different asymptotic running times?

Part 4: Algorithm Analysis Continued... 5. Given the following algorithms below, give a f(n) such that R(n) O(f(n)) where R(n) is the running time for input of size n. For each problem, you must provide justification. Proper justification must include i) a written explanation and ii) a diagram and/or mathematical reasoning.

a. R(n) is the running time of two_sum, where n is the length of arr.

public static boolean two_sum(int[] arr) { for (int i=0; i

public static void printItA(int n){ for(int i = 0; i < n; i++) { for(int j = 0; j < n; j*=2) { System.out.println("Something"); } } } c. R(N^a,N^b) is the running time of inside, in terms of Na and Nb, the lengths of the arrays a and b.

private static double[] inside(double[] a, double[] b) { double[] c = new double[a.length]; int i = 0, j = 0; for (int k = 0; k < c.length; k++) { if (i < a.length) { if (j < b.length) { if(a[i] <= b[j]) { c[k] = a[i]; } else { c[k] = b[j]; } } else { c[k] = a[i]; i++; } } else { if (j < b.length) { c[k] = b[j]; j++; } } } return c; } d. R(N) is the running time of outside, in terms of N, the length of list. Use your answer from (c) for the running time of one call to inside.

public static double[] outside(double[] list) { int x = list.length; if (x <= 1) return list; double[] a = new double[x/2]; double[] b = new double[x - x/2]; for (int i = 0; i < a.length; i++) { a[i] = list[i]; } for (int i = 0; i < b.length; i++) { b[i] = list[i + x/2]; } return outside(inside(a, b));