reshown by
328 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("*");

         }

}
reshown by

1 Answer

Best answer
1 votes
1 votes

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

Related questions

0 votes
0 votes
4 answers
3
iita asked Dec 31, 2016
563 views
1 votes
1 votes
2 answers
4
neeraj asked May 31, 2016
1,889 views
void fun(int n, int k) { for (int i=1; i<=n; i++) { int p = pow(i, k); for (int j=1; j<=p; j++) { // Some O(1) work } }}