Big O analysis for this for loop

big-o, code-analysis, for-loop, java, time-complexity

Solution

I would say its O(N^4) as its 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

Problem

``` 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++; } } } ``` } The above got me confusing ``` 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 ``` Therefore roughly I could be looking at O(N^5) . I am not sure. Please help clarify. EDIT I was wondering the runtime at the `if(j%i==0)`. Since it takes `N^2` inputs from its parent loop it could be doing `(N^2)/c` executions instead of `N/c`

Original source