Finding worst-case running time of Max Subsequence Sum Algorithm

[pocku]

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?

[sarehu]

You can always do a replacement that produces a bigger value, when finding a big O bound. For example, consider:

i = 1
while i < n {
  for j in (0..i) {
    print j
  }
  i = i * 2
}

We can note that the running time of print j is 1. The for loop runs i times, which means it takes i steps. Then i = i * 2 takes some constant number of steps, so we have i + 1 steps inside the while loop. We know that i < n, so we can substitute a larger value, n+1, for the number of steps inside the loop. Then, the loop runs log_2 (n) times, which means we have (n+1)*log_2(n) performance, i.e. our algorithm is O(n*log n).

And this is true. The algorithm I showed is O(n*log n). It's also O(n*n) and O(n*n*n).

If we wanted to know the tightest upper bound, we couldn't indiscriminately replace "i+1" with a larger number of steps, though. The running time of the algorithm above is O(n).

So regarding your question about whether you can perform that replacement: Yes, you can perform the replacement.

I don't think it's the place you'd want to perform the replacement, though. You can evaluate that expression easily: The expression inside the sum doesn't reference the iteration variable at all, so Sum(from i = 0 to j)(T0(n)+5) = (j+1)*(T0(n)+5) = (j+1)*(5n+12).

Then you can say T1(n) <= (n+1)*(5n+12); T1(n) is O(n^2).

= 5(j-i)+7
= 5n+7

I really wish you'd use <= when you mean an inequality, or else you'll be thinking in terms of substitutions and how to plug and chug a solution, rather than the facts you are writing on paper.

[pocku]

I don't quite get it. (j+1) is the number of time the loop runs and n is the number of elements you have in the array so wouldn't substituting the n in mean running the loop (n+1) times?

[pocku]

I really wish you'd use <= when you mean an inequality, or else you'll be thinking in terms of substitutions and how to plug and chug a solution, rather than the facts you are writing on paper.

The honest truth is, I don't know when an inequality sign or when an equal sign should be used. I'm struggling to understand algorithm analysis. I more or less understand the examples in my text book but I'm pretty much lost when it comes it doing it on my own since I don't know when a substitution should be used or how to deal with loops and summations.

[sarehu]

Nobody knows when a substitution should be used. Problem solving works by guessing what steps to do and seeing where it leads, and you can only get better at guessing with experience.

You should use inequality operators when using "=" would be untrue.