0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ "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 :( $\endgroup$ May 7 '20 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.