For all algorithms give the analysis for the worst-case time bound. Read the problem statements carefully. You cannot use hashing

Given is an array A of size n containing integers in arbitrary order and an integer T. Determine whether there exist two indices i and j, 1 i < j n, such that 0 A[i] + A[i + 1] + . . . + A[j] T. For example, for A = [3, 5, 10, -13, 1, 4, 16] and T=2, a solution exists for i = 3 and j = 6 with 10 13 + 1 + 4 = 2 T.

Describe and analyze a Divide-and-Conquer algorithm solving the problem in O(n log n) time. Additional O(n) space can be used. Clearly state what a recursive call returns and how the combine step works. Note: You will get partial credit for an O(n log^2 n) time solution. No credit will be given for a quadratic time solution.