what is the time complexity of below code ?

Question

foo(int n)
{
  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("hii");
       }
}

 

How to proceed here for analyzing the time complexity ?

Answer 1

First of all , you can't start from i=0, as it will give divide by 0 error.

Now, modifying the problem to start from i=1.

Since, the innermost loop will be executed, only when j is a multiple of i.

So, for i = 1, the inner most loop will execute 1 times.

 

Total = 1

For i =2 , the innermost loop will execute for j=2,4 

       For j = 2 : it will execute 2 times 

      For j = 4 : it will execute 4 times.

Total = (2 + 4)

 

For i = 3, the innermost loop will execute for j = 3,6,9

       For j = 3, it will execute 3 times

        For j = 6, it will execute 6 times

        For j = 9, it will execute 9 times.

Total = 3 + 6 + 9

Now, you can observe the pattern. 

For i = m, the innermost loop will execute m times, for values of j = m, 2m, 3m, ... , m²

 

It's an arithmetic progression, so, total = $\frac{m}{2}$(m + m²)

Now, for i = 1, to n, take the summation of this.

$\sum_{m=1}^{n}\frac{m}{2}(m+m^{2}) = \sum \frac{m^{3}}{2} + \sum \frac{m^{2}}{2} = O(n^{4})$

Answer 2

i=0	i=1	i=2	i=3	i=n-1
j=0 times	j=1 time(j=1)	j=4 times(j=1,2,3,4)	j=9 times(1,2,3,4,5,6,7,8,9)	j=(n-1)^2 times(1,2,3,4....)
k=0 times	k=1 times	k=2+4 times	k=(3+6+9) times	k=(sum of all multiple of i) times

hence number of times inner loop executed=0+(1)+(2+4)+(3+6+9)+.......(p+2p+.....p²⁾

^{nth term =p/2(p+p2)}

sum the series form p=0 to p=n-1

so time complexity =O(n⁴)