recategorized by
1,242 views
3 votes
3 votes
what will be time complexity of this program?

void function(int n)
{
    int count = 0;
    for (int i=0; i<n; i++)
    {
        for (int j=1; j< i*i; j++)
        {
            if (j%i == 0)
            {
                for (int k=0; k<j; k++)
                    printf("*");
            }
        }
    }
}
recategorized by

3 Answers

4 votes
4 votes

Answer: $O(n^4)$

The “printf("*");” statement is running the maximum no. of times. So, the Time complexity is actually how many times the “printf("*"); statement is running. I have unraveled every loop so that the actual number of execution can be determined and to prove that the program is actually depending on the $if$ statement:-

So the “printf("*");” statement is running $O(n^4)$ times, The time complexity of the program is $O(n^4)$. 

–1 votes
–1 votes

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

Here the innermost loop will run maximum when

j=(n^2)-1   

so the T.C of innermost loop will be  =  O(n^2)

now the middle loop 

i.e   for (int j=1; j< i*i; j++)

this will run maximum when i=n-1

and as the constraint here is  j<i*i  thus   T.C = O(n^2)

now coming to the outermost loop it is clearly running n times

thus T.C = O(n)

the overall T.C = n*n^2*n^2

it will be O(n^5). 

Related questions

0 votes
0 votes
0 answers
1
amit166 asked Nov 15, 2018
386 views
If $A$ is $2\times 2$ matrix ,eigen value is $1,-2$ and corresponding eigen vector $[1,2]^{T}$ and $[9,1]^{T}$.find sum of element of the matrix $A.$
0 votes
0 votes
1 answer
2
yogeshsingh asked Aug 15, 2023
388 views
int fun1( int n ){ int i , j , p =0, q =0; for( i =1 ; i < n ; ++i) { for( j =n ; j 1; j = j/2) ++p; for( k =n ; k p; k ...
0 votes
0 votes
2 answers
3
raja11sep asked Feb 13, 2022
838 views
Can anyone explain this?
0 votes
0 votes
1 answer
4