CODEWITHSUNDEEP
javafor-loopbig-otime-complexitycode-analysis
jmishra
jmishra

Reputation: 2081

Big O analysis for this for loop

 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

Upvotes: 4

Views: 1788

Answers (3)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

I think the answer, using Sigma notation, would be like the following:

enter image description here

Upvotes: 0

Tomasz Nurkiewicz
Tomasz Nurkiewicz

Reputation: 340733

@PeterLawrey did the math, here are benchmarks plotted on chart (my data set - n vs. execution time in microseconds).

Basically I run the code in question several times with different n input (X-axis). Then I divided average execution time by n^5, n^4 and n^3 functions and plotted that:

enter image description here

Full size image

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

Guess what, avergae execution time t(n) divided by n^5 keeps getting decreasing, while t(n)/n^3 keeps growing. Only t(n)/n^4 is stabilizes when approaching infinity which proves that the average execution time is in fact O(n^4).

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533510

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

Upvotes: 6

Related Questions