Can you find the time complexity of this piece of code?

Question

I have tried to find but my answer doesn't match with the solution in the text.

Could anyone explain me to find the time complexity?

for (int i=0; i<n; i++)
        for (int j=i; j< i*i; j++)
            if (j%i == 0)
            {
                for (int k=0; k<j; k++)
                    printf("*");
            }

Yes. Can you? Show what you tried. Please go over [how to ask](https://stackoverflow.com/help/how-to-ask) and [on-topic](https://stackoverflow.com/help/on-topic) again and if you have questions provide your code as [mvce](https://stackoverflow.com/help/mcve). — Patrick Artner, Mar 07 '18 at 15:58
Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Patrick Artner, Mar 07 '18 at 15:58
What *is* your answer and how did you come up with it? What is the solution in the text? — JJJ, Mar 07 '18 at 16:04
As luck would have it, this code measures its own complexity. Try it for different values of `n`, count stars, and see if you can find a correlation. — Jeroen Mostert, Mar 07 '18 at 16:04

score 1 · Accepted Answer · answered Mar 07 '18 at 17:36

Let f(n) be the number of operations aggregated from the outer loop,
Let g(n) be the number of operations aggregated at the level of the first inner loop.
Let h(n) be the number of operations performed at the level of the third (most inner) loop.

Looking at the most inner loop

for (int k=0; k<j; k++)
   printf("*");

We can say that h(j) = j.

Now, as j varies from i to i*i, the following values of i satisfy i%j = 0, i.e. i is a multiple of j:

j = 1.i
j = 2.i
j = 3.i
...
j = (i-1).i

So

g(i) = sum(j=i, j<i^2, h(j) if j%i=0, else 0)
     = h(i) + h(2.i) + ... + h((i-1).i)
     = i + 2.i + ... + (i-1).i
     = i.(1 + 2 + ... + i-1) = i.i.(i-1)/2
     = 0.5i^3   // dropped the term -0.5i^2 dominated by i^3 as i -> +Inf

=> f(n) = sum(i=0, i<n, g(i))
        = sum(i=0, i<n, 0.5i^3)
       <= sum(i=0, i<n, 0.5n^3)
       <= 0.5n^4

=> f(n) = O(n^4)

Thank you very much I had been stumped by this problem – tnxy Mar 07 '18 at 17:40 — tnxy, Mar 07 '18 at 17:40

user3666197 · Answer 2 · 2018-03-08T16:27:12.980

Could anyone explain me how to find the time complexity?

A posted claim of cited O( N^5 ) was not supported by experimental data.

Best start with experimentation on low scale:

for (         int aScaleOfBigO_N  =          1;
                  aScaleOfBigO_N <  2147483646;
                  aScaleOfBigO_N *=          2
                  ){        
    printf( "START: running experiment for a scale of N( %d ) produces this:\n",
                  aScaleOfBigO_N
                  );
    int letsAlsoExplicitlyCountTheVisits = 0;
    for (     int i = 0; i <  aScaleOfBigO_N; i++ )
        for ( int j = i; j <  i*i;            j++ )
            if (  j % i == 0 )
            {
                for ( int k = 0; k < j; k++ )
                {
                 // printf( "*" );                       // avoid devastating UI
                    letsAlsoExplicitlyCountTheVisits++;
                }
            }
    printf( "  END: running experiment visits this many( %d ) times the code\n",
                   letsAlsoExplicitlyCountTheVisits
                   );
}

Having collected some reasonably large amount of datapoints ( N, countedVisits ), your next step may be to fit the observed datapoints and formulate the best matching O( f(N) ) function of N.

That can go this simple.

START: running experiment for a scale of N(           1 )
  END: running experiment visits this many(           0 ) times the code.
START: running experiment for a scale of N(           2 )
  END: running experiment visits this many(           0 ) times the code.
START: running experiment for a scale of N(           4 )
  END: running experiment visits this many(          11 ) times the code.
START: running experiment for a scale of N(           8 )
  END: running experiment visits this many(         322 ) times the code.
START: running experiment for a scale of N(          16 )
  END: running experiment visits this many(        6580 ) times the code.
START: running experiment for a scale of N(          32 )
  END: running experiment visits this many(      117800 ) times the code.
START: running experiment for a scale of N(          64 )
  END: running experiment visits this many(     1989456 ) times the code.
START: running experiment for a scale of N(         128 )
  END: running experiment visits this many(    32686752 ) times the code.
START: running experiment for a scale of N(         256 )
  END: running experiment visits this many(   529904960 ) times the code.
START: running experiment for a scale of N(         512 )
  END: running experiment visits this many(  8534108800 ) times the code.
START: running experiment for a scale of N(        1024 )
  END: running experiment visits this many(136991954176 ) times the code.
START: running experiment for a scale of N(        2048 )
...

Experimental data show about this algorithm time-complexity behaviour in-vivo:

Can you find the time complexity of this piece of code?

2 Answers2

Could anyone explain me how to find the time complexity?