# Algorithm Analysis of Three nested loop

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.

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.

• "Innermost counts as another n for big O purposes even if you’re looking at n^2 (n-1)/2 sort of deal." Can you explain a little more please I'm still confused :( May 7 '20 at 3:08