in Programming reshown by
166 views
0 votes
0 votes
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("*");

         }

}
in Programming reshown by
by
166 views

1 Answer

1 vote
1 vote
Best answer

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

Total time = 2*1 + 3*(1+2) + 4*(1+2+3) + 5*(1+2+3+4) +………..                       ….+ (n-1)*(1 + 2 + 3 +…….+ n-2 )

                = ​ ∑(j=2 to n-1) [j * ∑(k=1 to j-1) k]

                 =  ∑(j=2 to n-1)[ j*(j-1)*j/2]      ………….  let m=(j-1)

                 = ½ (m=1 to n-2) [ m*(m+1)^2 ]

                 = ½ (m=1 to n-2)[ m^3 + 2m^2 + m ]

              = ½ ((n-2)*(n-1)/2)^2 +  2*(n-2)*(n-1)*(2n-3)/6  + (n-2)*(n-1)/2

              => O(n^4)

selected by

3 Comments

edited by
thnx
1
1
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}$

(+1) for the Answer.
1
1
Yes you are right …… I think the complexity will be n^2 times more ….. let me solve it again…… Thanks
1
1