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
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?