current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

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.

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

1 Answer 1

up vote 0 down vote

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;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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