Great O analysis for this cycle

Question

sum = 0; for (i = 1; i <= n; i++) { //#1 for (j = 1; j <= i * i; j++) { //#2 if (j % i == 0) { //#3 for (k = 1; k <= j; k++) { //#4 sum++; } } } 

}

Because of this, I got confused

 Suppose #1 runs for N times #2 runs for N^2 times #3 runs for N/c since for N inputs N/c could be true conditions #4 runs for N times 

So roughly I could look at O ​​(N ^ 5). I'm not sure. Please help clarify.

EDIT I was interested in working with the if(j%i==0) tag if(j%i==0) . Since it accepts inputs N^2 from its parent cycle, it can execute (N^2)/c execution instead of N/c

Answer 1

I would say that its O (N ^ 4) is the same as.

  for (int i = 1; i <= n; i++) //#1 O(n ... for (int j = i; j <= i * i; j+=i) //#2 ... * n ... for (int k = 1; k <= j; k++) //#4 ... * n^2) as j ~= i^2 sum++; 

or

 public static void main(String... args) { int n = 9000; System.out.println((double) f(n * 10) / f(n)); } private static long f(long n) { long sum = 0; for (long i = 1; i <= n; i++) //#1 for (long j = 1; j <= i; j++) //#2 sum += i * j; // # 4 return sum; } 

prints

 9996.667534360826 

which is pretty close to 10 ^ 4

Answer 2

@PeterLawrey did the math, here are the graphs on the graph ( my dataset is n compared to the runtime in microseconds).

Basically, I run the specified code several times using another input n (X axis). Then I divided the average runtime into functions n^5 , n^4 and n^3 and built it like this:

^{Full size image}

Note that this is a logarithmic scale and that all functions are scaled to more or less in the same range.

Guess that the runtime avergae t(n) divided by n^5 continues to decrease, and t(n)/n^3 continues to grow. Only t(n)/n^4 stabilizes when approaching infinity, which proves that the average execution time is actually O(n^4) .

Answer 3

I think the answer using Sigma notation would look like this: