// A[1...n] is an array of n elements function fun (A[]) function sum (A[], i) temp...

Transcribed Image Text:

// A[1...n] is an array of n elements function fun (A[]) function sum (A[], i) temp [n] 1. Create new array 2. temp [1] A[1] ; k=2; 3. for (i=2; i<n; i++) 4. 5. 6. 7. if (A[i] >= sum (A, 1)) temp [k] =A[i]; k++; return temp [] 1. s= 0 2. for (j-1; j<i; j++) s += A[j] 3. 4. return s 1. [15 points] Consider the algorithm shown above. a) (2 pts) What does the algorithm do? Justify your answer. b) (2 pts) What is the output of the algorithm on input array A = [1, 3, 5, 7, 15, 2, 4, 40, 50, 100]? c) (4 pts) Analyze the algorithm and determine its running time as a function of n. Use the Big-O() notation and consider the behavior of the algorithm on the worst possible input.. d) (7 pts) Come up with a better algorithm for the same problem. For example if your algorithm in part (c) was (say) O(n), you should produce an algorithm that is strictly less than O(n), like O(n) or O(n²), etc... // A[1...n] is an array of n elements function fun (A[]) function sum (A[], i) temp [n] 1. Create new array 2. temp [1] A[1] ; k=2; 3. for (i=2; i<n; i++) 4. 5. 6. 7. if (A[i] >= sum (A, 1)) temp [k] =A[i]; k++; return temp [] 1. s= 0 2. for (j-1; j<i; j++) s += A[j] 3. 4. return s 1. [15 points] Consider the algorithm shown above. a) (2 pts) What does the algorithm do? Justify your answer. b) (2 pts) What is the output of the algorithm on input array A = [1, 3, 5, 7, 15, 2, 4, 40, 50, 100]? c) (4 pts) Analyze the algorithm and determine its running time as a function of n. Use the Big-O() notation and consider the behavior of the algorithm on the worst possible input.. d) (7 pts) Come up with a better algorithm for the same problem. For example if your algorithm in part (c) was (say) O(n), you should produce an algorithm that is strictly less than O(n), like O(n) or O(n²), etc...

Answer rating: 100% (QA)

1 Given Algorithm Analysis a What does the algorithm do Explanation The algorithm processes an input array A of n elements and creates a new array tem... View the full answer