Algorithmic complexity of naive code for processing all consecutive subsequences of a list: n^2 or n^3?

Question

I'm studying for a test and found this question:

I can't really determine the complexity, I figured it's either O(n²) or O(n³) and I'm leaning towards O(n³).
Can someone tell me what it is and why?

My idea that it's O(n²) is because in the j loop, j = i which gives a triangle shape, and then the k loop goes from i + 1 to j, which I think is the other half of the triangle.

public static int what(int[] arr)
{
    int m = arr[0];
    for (int i=0; i<arr.length; i++)
    {
        for (int j=i; j<arr.length;j++)
        {
            int s = arr[i];
            for (int k=i+1; k<=j; k++)
             s += arr[k];
            if (s > m)
             m = s;
        }
    }
    return m;
}

Also if you can tell me what it does?

I figured it returns the addition of positive integers or the biggest integer in the array.
But for arrays like {99, -3, 0, 1} it returns 99, which I think is because it's buggy. If not than I have no Idea what it does:

{99, 1} => returns 100
{-1, -2, -3} => return -1
{-1, 5, -2} => returns 5
{99, -3, 0, 1} => returns 99 ???

Answer 1

You can proceed methodically, using Sigma Notation, to obtain the order of growth complexity:

Answer 2

You have 3 for statements. For large n, it is quite obvious that is O(n^3). i and j have O(n) each, k is a little shorter, but still O(n).

The algorithm returns the biggest sum of consecutive terms. That's why for the last one it returns 99, even if you have 0 and 1, you also have -3 that will drop your sum to a maximum 97.

PS: Triangle shape means 1 + 2 + ... + n = n(n+1) / 2 = O(n^2)

Answer 3

Code:

for (int i=0; i<arr.length; i++) // Loop A
{
    for (int j=i; j<arr.length;j++) // Loop B
    {
        for (int k=i+1; k<=j; k++) // Loop C
        {
            // ..
        }
    }
}

Asymptotic Analysis on Big-O:

Loop A: Time = 1 + 1 + 1 + .. 1 (n times) = n

Loop B+C: Time = 1 + 2 + 3 + .. + m = m(m+1)/2

Time = SUM { m(m+1)/2 | m in (n,0] }

Time < n * (n(n+1)/2) = 1/2 n^2 * (n+1) = 1/2 n^3 + 1/2 n^2

Time ~ O(n^3)

Answer 4

No matter triangle shape or not, it always a complexity O(N^3), but of course with lower constant then a full triple nested cycles.

Answer 5

You can model the running time of the function as

sum(sum(sum(Theta(1), k=i+1..j),j=i..n),i=1..n)

As

sum(sum(sum(1, k=i+1..j),j=i..n),i=1..n) = 1/6 n^3  - 1/6 n,

the running time is Theta(n^3).

Answer 6

If you do not feel well-versed enough in the underlying theory to directly apply @MohamedEnnahdiElIdri's analysis, why not simply start by testing the code?

Note first that the loop boundaries only depend on the array's length, not its content, so regarding the time complexity, it does not matter what the algorithm does. You might as well analyse the time complexity of

public static long countwhat(int length) {
  long count = 0;
  for (int i = 0; i < length; i++) {
    for (int j = i; j < length; j++) {
      for (int k = i + 1; k <= j; k++) {
        count++;
      }
    }
  }
  return count;
}

Looking at this, is it easier to derive a hypothesis? If not, simply test whether the return value is proportional to length squared or length cubed...

public static void main(String[] args) {
  for (int l = 1; l <= 10000; l *= 2) {
    long count = countwhat(l);
    System.out.println("i=" + l + ", #iterations:" + count + 
      ", #it/n²:" + (double) count / l / l +
      ", #it/n³:" + (double) count /  l / l / l);
  }
}

... and notice how one value does not approach anyconstant with rising l and the other one does (not incidentally the very same constant associated with the highest power of $n$ in the methodological analysis).

Answer 7

This requires O(n^3) time due to the fact that in the three loops, three distinct variables are incremented. That is, when one inside loop is over, it does not affect the outer loop. The outer loop runs as many times it was to run before the inner loop was entered.

And this is the maximum contiguous subarray sum problem. Self-explanatory when you see the example:

{99, 1} => returns 100
{-1, -2, -3} => return -1
{-1, 5, -2} => returns 5
{99, -3, 0, 1} => returns 99

There is an excellent algorithm known as Kadane's algorithm (do google for it) which solves this in O(n) time.

Here it goes:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

References: 1, 2, 3.

Answer 8

O(n^3).

You have calculated any two item between arr[0] and arr[arr.length - 1], running by "i" and "j", which means C(n,2), that is n*(n + 1)/2 times calculation.

And the average step between each calculation running by "k" is (0 + arr.length)/2, so the total calculation times is C(n, 2) * arr.length / 2 = n * n *(n + 1) / 4, that is O(n^3).

Answer 9

The complete reasoning is as follows:

Let n be the length of the array.

1) There are three nested loops.

2) The innermost loop performs exactly j-i iterations (k running from i+1 to j inclusive). There is no premature exit from this loop.

3) The middle loop performs exactly n-j iterations (j running from i to n-1 inclusive), each involving j-i innermost iterations, in total (i-i)+(i+1-i)+(i+2-i)+... (n-1-i) = 0+1+2... + (n-1-i). There is no premature exit from this loop.

4) The outermost loop performs exactly n iterations (i running from 0 to n-1 inclusive), each involving 0+1+2+ ... (n-1-i) innermost iterations. In total, (0+1+2... n-1) + (0+1+2+... n-2) + (0+1+2+... n-3) + ... (0). There is no premature exit from this loop.

Now how do handle handle this mess ? You need to know a little about the Faulhaber's formula (http://en.wikipedia.org/wiki/Faulhaber%27s_formula). In a nutshell, it says that the sum of integers up to n is O(n^2); and the sum of the sum of integers up to n is O(n^3), and so on.

If you recall from calculus, the primitive of X is X^2/2; and the primitive of X^2 is X^3/3. Every time the degree increases. This is not by coincidence.

Your code runs in O(n^3).