Algorithm Analysis of Three nested loop

Question

I'm trying to figure out Time function and Big O of a nested loop code,

public static int example5(int[ ] first, int[ ] second) { // assume equal-length arrays
  int n = first.length, count = 0;
  for (int i=0; i < n; i++) { // loop from 0 to n-1
    int total = 0;
    for (int j=0; j < n; j++) // loop from 0 to n-1
      for (int k=0; k <= j; k++) // loop from 0 to j
      total += first[k];
  if (second[i] == total) count++;
}
  return count;
}

According to my calculations the time function should lie in $n^4$, but the right answer is $n^3$.
Here are my solution steps,

1. Constant operations = 2 times
   
2. i-loop = 0 to n-1 = n times (although it's 2n+2, but I would pick the most higher order term)
   
3. Constant operation = 1 time
   
4. j-loop = 0 to n-1 = n x n times = $n^2$ times
5. k-loop = 1+2+3+...+n-1+n = n x n x $n\frac{n+1}{2}$ times = $\frac{n^4 + n^3}{2}$ times

What I'm doing wrong, can someone please point out.

Answer 1

Three for loops gets you to n^3.

EDIT:

for (int i=0; i < n; i++) // first n ..etc.. for (int j=0; j < n; j++) // second n ...etc...

Outer two are n, that makes n^2 so far. Next look at inner loop:

for (int k=0; k <= j; k++) // third n

Innermost counts as another n for big O purposes even if running k to j instead of k to n. You're still on the order of n^3.

For that inner loop you're doing 1 + 2 + 3 ... loops as j iterates, so strictly speaking it's not exactly n^3 iterations, but n * n * (n+1)/2, but for big O purposes don't let that throw you off, it's n^3, the (n+1)/2 piece is just another layer of n. If n was 1,000,000 you'll end up with "on the order of" 10^18 loops.

Hope this helps.