unacademy combat

Question

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 1

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

Comments

samarpita

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.

---

@Pranavpurkar 

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

---

samarpita

got it! yes you are correct!

Answer 2

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

Comments

but in above question j is starting from 1 not i

Answer 3

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

Comments

@Pranavpurkar   then what about if condition

---

Take the worst case here, as we are looking for the time complexity thus ,

it is possible that the if condition is true when j=n^2(approx)  and i=n(approx)  thus (j%i==0).

and it will enter the if condition and innermost loop will run till n^2.

 

---

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

---

That was a blunder from my side buddy! Thanks.

just one doubt .

for i=0 , I think it will not even execute the second loop right?

as when i=0 → j=1  and 1%0==not defined thus will not enter the inner loop so 0 printf statements right?

---

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

---

@Pranavpurkar Thanks for pointing. Corrected :)

---

Abhrajyoti00

Thanks for correcting me too brother :)

next time have to analyze carefully.

---

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

---

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

---

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;

               }}}}

In this case time complexity will be $\Theta (n^{3})$

---

@samarpita

Here the i value will get updated even for the outer loop no? if it is getting updated inside as all are same variables .

won’t it be a problem?

---

@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?

---

@samarpita @Nisha Bharti how ?

there is no dependency between loops 

---

inner most loop will be executed $n^{3}$ with every j value till every $n^{2}$

Edit 

There is only 1 variable i  that will be initialised again with every loop 

---

@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

---

someone pls explain this question clearly not getting it correct.

---

@Nisha Bharti oh sry it's O($n^{^{3}}$)

---

@Abhrajyoti00 yes, you are correct. 

---

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

---

 Argharupa Adhikary

can you show the exact solution?