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.

Dark Mode

524 views

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

1

–1 vote

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

0

edited
Sep 27, 2022
by Abhrajyoti00

Ah! This question was really a good one yesterday. Although it’s actually Θ(n^4), but even O(n^5) is not wrong. @Pranavpurkar Your method is correct if the loops are independent.

But for dependent loops, we need to postmortem the printf statement.

Carefully calculating the no of times printf statement is executed, we’ll see it to be:-

$i=0$ → 0 time

$i=1$ → 1 time

$i=2$ ; $j = 1,2,3,4$ printf runs for : 2+4 = 2(1+2) times

$i=3 $ ; $j = 1,2,3,4,5,6,7,8,9$ printf runs for : 3+6+9 =3(1+2+3) times

Hence, $\sum_{i=1}^{n}(i^3 + i^2) = O(n^4)$

Since there were options yesterday, $O(n^4)$ should have been the correct answer to it.

This q was asked before also: big o - Why is the runtime of this code O(n^5)? - Stack Overflow

**Edit: i=0 -> 0 times**

2

1

Yes @Pranavpurkar inner loops won't execute\\ \\ \\ $\begin{bmatrix} Iteration &i &j &k \\ 1& 0\ ( 1 time)&X &X \\ 2& 1(1 time) &1(1time) & 0(1 time)\\ 3& 2(2times)& 1,2,3,4(4 times)& 2,4(2 times)\\ ....\\ &n& n^{^{2}}& n \end{bmatrix}\\ \ n*n^{^{2}}*n=n^{_{^{4}}} \ \\ time \ complexity=\Theta (n^{^{4}})$

0

@samarpita I didn’t read the link though. Seemed similar.

But the process you have done for the last loop seems incorrect. Last loop doesn’t **always **run from 1 to j. It runs only when the $if$ becomes true. And if you break the loop, you’ll see the series as I got.

0

@Abhrajyoti00 brother here for i=1 also the innerloop won’t execute becoz the constraint in the 2^{nd} loop is** j<i^2** and for i=1 it will be ** for(j=1;j<1*1;j++)** which is not satisfied. :(

thus 0 printf when i=1.

0

1

0

@samarpita yes it will be O(n^3),

main(){

int i;

for(i=1; i<=n; i++);

for(i=1; i<= n^2 ; i++);

for(i=1; i<=n^3 ; i++)

{

x=y+z;

}}

and now what will be the complexity?

0

@afroze where is j? i am asking other question as the 2 outer loop terminated within the loop,

then again complexity will be n^3

0

edited
Sep 27, 2022
by Argharupa Adhikary

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.

1