44

I'm working on a data structures course and I'm not sure how to proceed w/ this Big O analysis:

sum = 0;
for(i = 1; i < n; i++)
     for(j = 1; j < i*i; j++)
         if(j % i == 0)
             for(k = 0; k < j; k++)
                   sum++;

My initial idea is that this is O(n^3) after reduction, because the innermost loop will only run when j/i has no remainder and the multiplication rule is inapplicable. Is my reasoning correct here?

amit
  • 175,853
  • 27
  • 231
  • 333
user2986376
  • 451
  • 3
  • 5

1 Answers1

50

Let's ignore the outer loop for a second here, and let's analyze it in terms of i.

The mid loop runs i^2 times, and is invoking the inner loop whenever j%i == 0, that means you run it on i, 2i, 3i, ...,i^2, and at each time you run until the relevant j, this means that the inner loop summation of running time is:

i + 2i + 3i + ... + (i-1)*i  = i(1 + 2 + ... + i-1) = i* [i*(i-1)/2]

The last equality comes from sum of arithmetic progression.
The above is in O(i^3).

repeat this to the outer loop which runs from 1 to n and you will get running time of O(n^4), since you actually have:

C*1^3 + C*2^3 + ... + C*(n-1)^3 = C*(1^3 + 2^3 + ... + (n-1)^3) = 
= C/4 * (n^4 - 2n^3 + n^2)

The last equation comes from sum of cubes
And the above is in O(n^4), which is your complexity.

amit
  • 175,853
  • 27
  • 231
  • 333
  • 1
    inner loop do not run when `j = i^2` since j-loop end after loop body for `j = i^2 - 1` – hk6279 Mar 19 '15 at 20:13
  • 1
    @hk6279 Thank you. Obviously it does not influence the big O notation, but you're 100% correct. Fixed. – amit Mar 19 '15 at 20:15
  • 1
    I think this answer is missing a minor detail. You also need to count the number of times `j%i == 0` is checked. It turns out of course it is checked only `O(i^2)` times compared to `O(i^3)` executions of the innermost statement, so `O(i^3)` wins out. But if it the condition were instead something like `if (j <= 10)`, your analysis would be incorrect. – Caleb Stanford Mar 19 '15 at 21:12
  • 1
    @C-S I avoided it because it is pretty obvious this number is smaller (asymptotically) then `i^3`. – amit Mar 19 '15 at 21:17
  • @amit OK, but if someone wrote that it was "pretty obvious" on a CS theory problem set, I would dock them points ;) – Caleb Stanford Mar 19 '15 at 21:20