Summing sub arrays (maximal subarray)

I have this piece of code, and I want to make if the way I'm calculating the time complexity is valid:

void traverse() {
int currSum = 0;
for(int i = 0; i < original.length; i++) {
currSum = original[i];
for(int j = i + 1; j < original.length; j++) {
if(max <= currSum) {
max = currSum;
}
currSum += original[j];
}

if(max <= currSum) {
max = currSum;
}
}
}


I was thinking it'd be something along the lines of: (n - 1) + (n - 2) + (n - 3) ... etc but wasn't sure if that's correct.

• does the code work?
– Malachi
Aug 12, 2015 at 20:14
• The complexity is O(n2). If that was your question.
– Emz
Aug 13, 2015 at 0:08
• @Malachi yes, it does Aug 13, 2015 at 16:20
• @Emz do you mean n^2? Aug 13, 2015 at 16:20
• See my answer to the question.
– Emz
Aug 13, 2015 at 19:19

1 Answer

The complexity of your void traverse () method is O(n^2).

The question is how many times if you have n-elements will currSum += original[j]; be performed.

To calculate that in this case you simply check how many times each loop will be executed.

The outer loop is n-times. Based on the length. Now the inner loop depends both directly and indirectly on the outer loop. As it will be performed n times based on the outer loop and (n/2)-1 times based on its condition.

So the total time is (n^2)/2-1 which is written O(n^2).

If this wasn't your question you should update it to make it more clear.

This is not a complete answer. If this satisifies as an answer then it should be moved to Stack Overflow. As it does not have anything to do with reviewing of code.

Some nitpick as well.

    if(max <= currSum) {
max = currSum;
}


Logically you would write it as

    if(currSum > max) {
max = currSum;
}


There is no real need to compare if they are equal and then give a new value (which will be equal to the old) if they are equal.

Now for the algorithm itself. If the problem is to find the maximum subarray I suggest you have a read over at Kadane's Algorithm, as it solves this in O(n) instead.

public int maxSubArray (int[] a) {
int max = 0;
int cur = 0;
for (int i : a) {
max = Math.max (i, max + i);
cur = Math.max (cur, max);
}
return max;
}