480 views
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("*");
}
}
}
}

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)$.

I  think  i^2-1 is correct because in the loop the constraint is j<i^2

Here I am talking  only about  the second loop.

yeah it’s true that j will go till $i^{2}$-1 but when j= $i^{2}$-1 then (j%i$\neq$ 0).

Last value when (j%i ==0 ) will be i(i-1)=  $i^{2}-i$. After that again (j%i==0) will be at $i^{2}$.

Just take a sample example:

Let i=4, so i*i = 16.

So, (j%i==0) will be when j=4,8,12(not considering 16 bcz j< i*i).

got it! yes you are correct!

Time complexity is O($n^{5}$)

1 comment

but in above question j is starting from 1 not i

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).

edited

Dear @samarpita

$\sum_{i=1}^{n} \sum_{j=1}^{i^{2}-1}\sum_{k=1}^{j}1$

Here the last summation i.e. $\sum_{k=1}^{j}1$ is partially correct, Because the effect of $if$ statement is not displayed here. It should be $\sum_{k=1}^{j}1$ whenever j%i == 0 condition is true. Which decreases the time complexity from $O(n^5)$ to $O(n^4)$

Actually the K loop is not exactly running from (1 to j), we consider the K loop only when the if condition is true.

@samarpita

In worst case also the k loop will not run for every value of J, here also the $i$f statement has a major role, We consider the k loop only when the j value is multiple of i i.e. (j % i = 0).

can you show the exact solution?