Algorithm Analysis

1) The number of operation executed by algorithm A and B is 8n log n and 2n² respectively. Determine n₀ such that A runs faster than B for n great than equal to n₀.

2) What is the running time characterization of example1 in terms of input size n?

public static int example1(int[] arr){ int total =0; for(int i=0; i < arr.length; i++) total += arr[i]; return total; }

3) What is the running time characterization of example2 in terms of input size n? public static int example2(int[] arr){ int total =0; for(int i=0; i < arr.length; i+=2) total += arr[i]; return total; }

4) What is the running time characterization of example3 in terms of input size n? public static int example3(int[] arr){ int total =0; for(int i=0; i < arr.length; i++) for(int j = 0; j <=i; j++) total += arr[i]; return total; }

5) What is the running time characterization of example4 in terms of input size n? public static int example4(int[] arr){ int total = 0, prefix = 0; for(int i=0; i < arr.length; i++){ prefix += arr[i]; total += prefix; } return total; }

6) What is the running time characterization of example5 in terms of input size n? public static int example5(int[] first, int[] second){ int count = 0, total = 0; for(int i=0; i < first.length; i++){ total = 0; for(int j=0; j < first.length; j++) for(int k=0; k <= j; k++) total += first[k]; if(second[i]==total) count++; } return count; }