CODEWITHSUNDEEP
big-o
Pedro B
Pedro B

Reputation: 61

What's the Complexity of this Algorithm? BigO

I have the following algorithm:

for (i=0; i<=n-1; i++) {
    for (j=i; j<=n-1; j++) {
        sum = 0;
        for (k=i; k<=j; k++) {
            sum = sum + v[k];
        if (sum > max) max = sum;
        }
    }
}

The complexity of the first is O(n), the second is n-i, the third is j-i+1.

I know O(n^3) is an upper bound. But what's the true thing we can assume as complexity of this algorithm? Is it O(n^3)?

Thank you.

Upvotes: 1

Views: 82

Answers (2)

Andrzej Bobak
Andrzej Bobak

Reputation: 2112

It's O(n^3) in worst case (when i, j and k are of similar value). It's O(n) in best case, when j and k are 0 or 1:)

Since you have to be prepared for worst case data (and this is the main reason of examining complexity) you should assume O(n^3)

Upvotes: 1

varoStyle
varoStyle

Reputation: 46

I think O(n^3), the limits of the iterations doesnt matter.

Upvotes: 2

Related Questions