166 views
Find the complexity of the below function:

function (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("*");

}

}

Note: i runs from 0 to n-1 , j run from i to i^2 – 1 and k from 0 to j-1

So, For i=0 and 1 , j will not run at all.

For i=2,    j from 2 to 3 but will enter if statement only for j=2 so k runs from 0 to 1…... [2 times]

For i=3,    j from 3 to 8 but if statement valid for only j=3,6 so k runs from 0 to 2(for  j=3) and 0 to 5 (for j=6) ……..[(3+6) times= 3*(1+2) times]

so if you look at the pattern ….

For i=4    …….. [4*(1+2+3) times]

For i=5    ……...[5*(1+2+3+4) times]….. and so on

## => O(n^4)

edited by
thnx
you forgot to multiply $j$ in step $\sum_{j=2}^{n-1} (j-1)j/2$ from step $\sum_{j=2}^{n-1} j * \sum_{k=1}^{j-1}k$.

Generally, when we find any pattern, we have to prove it. Here it is easy to prove by induction.

For, $i=k,$ $T(k) = k \sum_{p=1}^{k-1}p = \frac{k*k*(k-1)}{2}$

Now, for $i=k+1,$ $T(k+1) = (k+1) \sum_{p=1}^{k}p = \frac{(k+1)*(k+1)k}{2}$

Yes you are right …… I think the complexity will be n^2 times more ….. let me solve it again…… Thanks