0
\$\begingroup\$

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.

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

1 Answer 1

1
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.