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,
- Constant operations = 2 times
- i-loop = 0 to n-1 = n times (although it's 2n+2, but I would pick the most higher order term)
- Constant operation = 1 time
- j-loop = 0 to n-1 = n x n times = $n^2$ times
- 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.
Solution
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.