Question 15 2 pts What is the worst-case time complexity of the algorithm given below? CountValuesLessThanT Input: a1, a2.,. n, the length of the sequence. T, a target value. Output: The number of values in the sequence that are ess than T count-O Fori 1 to n If (aT), count count + 1 End-for Return( count) O (n2) (n) o Q(1) O O(n2) O (n) Question 1 2 pts Which statement best describes an algorithm that takes as input a list of n integers and produces as output the largest difference obtained by subtracting an integer in the list from the one following it? O Set the answer to be 0. For i going from 1 through n-1, compute the value of the (n+1)st element in the list minus the nth element in the list. If this is larger than the answer, reset the answer to be this value. O Set the answer to be 0. For i going from 1 through n, compute the value of the (i+1)st element in the list minus the ith element in the list. If this is larger than the answer, reset the answer to be this value. O Set the answer to be 0. For i going from 1 through n, compute the value of the (i - 1)st element in the list minus the ith element in the list. If this is larger than the answer, reset the answer to be this value. O Set the answer to be 0. For i going from 1 through n-1, compute the value of the (i+1)st element in the list minus the ith element in the list. If this is larger than the answer, reset the answer to be this value. Question 2 2 pts To establish a big-O relationship, find witnesses C and k such that f(x) Is CIg(x) whenever x>k. Find the least integer n such that f (x) is O (xn) for the function f (x)-(x3 5log x) / (x* +1) O n 1 with witnesses C 6 and k0 n 1 with witnesses C = 6 and k = 1 O n -1 with witnesses C 6 andk 0 O n -1 with witnesses C-6 and k 1 Question 14 2 pts Simplify the recurrence relation below as much as possible. The explicit formula for the function should have the same asymptotic growth as the original recurrence relation. Which of the following answers is correct? o T (n) 3 . T (n) + 3n log n o T (n) 3- T(n/3) + (n) o T (n) -3. T (n/3) + 10n + log n o T(n) = 3. T (n/3) + (n log n) Question 12 2 pts What is the upper bound of the time complexity of the algorithm given below? MaximumSubsequenceSum Input: a1, a2 Output: The value of the maximum subsequence sum maxSum0 For = 1 to n n, the length of the sequence. thisSum := 0 For j-i to n thisSum thisSum a If ( thisSum > maxSum ), maxSum := thisSum End-for End-for Return( maxSum ) O (n2) o at n O ( n) 0(n2) O (1) Question4 2 pts f(n)4n25n6. Which choice for c and no are sufficient to prove that f is O(n2)? O c 9 and no1 O c 3 and no 2 Oc-5 and no 3 Oc 15 and no 1