Question & Answer: For all algorithms give the analysis for the worst-case time bound. Read the problem statements carefully. You cannot use hashin…..

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.

Don't use plagiarized sources. Get Your Custom Essay on
Question & Answer: For all algorithms give the analysis for the worst-case time bound. Read the problem statements carefully. You cannot use hashin…..
GET AN ESSAY WRITTEN FOR YOU FROM AS LOW AS \$13/PAGE

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.

1. Two loops in a row:
for (i = 0; i < N; i++) {
sequence of statements
}
for (j = 0; j < M; j++) {
sequence of statements
}

How would the complexity change if the second loop went to N instead of M?

2. A nested loop followed by a non-nested loop:
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
sequence of statements
}
}
for (k = 0; k < N; k++) {
sequence of statements
}

3. A nested loop in which the number of times the inner loop executes depends on the value of the outer loop index:
for (i = 0; i < N; i++) {
for (j = N; j > i; j--) {
sequence of statements
}
}