Summing sub arrays (maximal subarray)

Question

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.

Answer 1

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; }