I need help with finding a function T(n) that describes the upper bound for the worst case running time of this algorithm:

```
1. maxS = 0
2. n = A.length
3. for j from 0 to n − 1 do
4. for i from 0 to j do
5. S = 0
6. for k from i to j do
7. S+ = A[k]
8. end for
9. if S > maxS then
10. maxS = S
11. end if
12. end for
13. end for
```

This is what I’ve got so far (This is all new stuff to me and I have no idea whether I’m doing it right or not):

I started counting the cost of basic operations in the body of the inner-most for loop, which are: 2 ops. for incrementing k and 2 ops. for S+ = A[k], making a total of 4. Since the loop body is executed (j-i+1) times, this gives me 4(j-i+1). In addition, the test condition is executed (j-i+2) times and k is initially assigned to 0, thus:

T0(n) = (j-i+2) + 4(j-i+1) + 1

= j-i+2+4j-4i+4+1

= 5(j-i)+7

= 5n+7

I substituted (j-i) with n since that’s the worst-case number of steps that can be executed by the algorithm.

Then I moved on to the middle loop, where I've calculated its running time to be:

T1(n) = (j+2) + i= ∑(from i=0 to j) (T0(n)+5) + 1

where the number of iterations of this loop is at most j times. Since the worst-case is for the loop body to execute n times, can I replace ∑(from i=0 to j) with ∑(from i=0 to n-1) instead?