need help understanding code optimisation principle

[chi]

I've been scratching my head over this for a while so can anyone give me a hint?

say i've got an array A consisting of n integers A[0],A[1]......A[n-1], and i want to compute:
C [i][j] = A[i] + A[i + 1] +......+ A[j] for 0 <= i <= j < n.
The brute force algorithm would be something like this:

1. for i = 0,......,n-1
2.      for j = i,.....,n-1
3.           add up entries A[i] through A[j]
4.           store result in C[i][j]
5. return C

now i know the upperbound run time should be O(n^3), but dont understand how that works.

So far my line of thought is the first line runs n times, the second runs n times and the third is just the calculation so O(1) for that, and putting all that together:
n(n(1))=n^2?

[Zoltag]

My understanding is your example is O(N^2)

Check this site out - http://rob-bell.net/2009/06/a-beginn...ig-o-notation/

[~NJ]

Wouldn't something like

for(x=i, x<j, x++)
C[i][j] += A[x]

give you an O(N) first order execution time?

But I agree with Zoltag above that your example is O(N^2)

[Zoltag]

Originally Posted by ~NJ

Wouldn't something like

for(x=i, x<j, x++)
C[i][j] += A[x]

give you an O(N) first order execution time?

But I agree with Zoltag above that your example is O(N^2)

I believe so, though I doubt it would give the result OP is looking for.

[SLATYE]

I think his original example is indeed O(N³). The full code would look something like this:

for (i = 0; i < n; i++) {
   for (j = 0; j < n; j++) {
      C[i][j] = 0;
      for (k = i; k < j; k++) {
         C[i][j] += A[k];
      }
   }
}

(it doesn't look like that in his example because he just left the 'k' loop as "add up entries A[i] through A[j]"). Three loops suggests N³ scaling, unless there's something I'm missing.

I would presume that an optimisation would be this:

for (i = 0; i < n; i++) {
   for (j = 0; j < n; j++) {
      if (j <= i) {
         C[i][j] = 0; // Makes no sense to add from a larger index to a smaller.
      } else {
         C[i][j] = C[i][j - 1] + A[j];
      }
   }
}

(not tested, but it looks okay to me). That'd be N².

Edit: and I'm pretty sure that this problem cannot be reduced to anything less than N², simply because you have to fill every element in an n*n array.

[chi]

cheers for the help guys, after sleeping on it i think i've pieced it together

[akashra]

I know there's an SSE instruction to do what you describe here, I just can't think what it was. (was thinking phaddd, but no).