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

@Argharupa Adhikary Very well explained. This is exactly how it should be. The $if$ statement has a major effect.

---

@Pranavpurkar Here is the actual solution beautifully written.

---

@Argharupa Adhikary J=0 means?means for j loop how it is started from 0?

---

Abhrajyoti00 True:)

very well explained! finally got it.

just one correction is needed .

here when i=1 then j =0 instead of 1 bcoz j loop will not run as the given constraint is not satisfied.

---

@Pranavpurkar no when i=0 then j will be 1

---

@Nisha Bharti That won’t matter anyway. Ultimately $k \ loop $ is the sole-decider. Yes j will be $1$ first for $i =0$. But after that all are correct. Even the ending is absolutely correct at $1 \ to\ (n-1)^2-1$.

@Pranavpurkar Yes Buddy :) These qs always need loop unraveling. 

---

@Abhrajyoti00 yes now correct

---

@Abhrajyoti00 yes i was wrong and @Argharupa Adhikary yes you are correct.

It will be $\Theta (n^{4})$.

for (int k=0; k<j; k++)
                    printf("*");

This loop will run for $\Theta (j)$ time.

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

Here outer for loop will run for $\Theta (i^{2})$ times. In each iteration if (j%i ==0) satisfies, then the inner loop will run for $\Theta (j)$ time otherwise if it doesnot satisfy then it will be $\Theta (1)$.

So now we will analyze, that how many times this (j%i==0) will satisfy.

→ It will satisfy when j=i,2*i,3*i….(i-1)*i.

→ Therefore inner for loop will run when j=i,2*i,3*i….(i-1)*i.

→ So time complexity will be : i+2i+3i+…….+(i-1)*i

                                              = i(1+2+3+…..+(i-1)) = $\Theta (i^{3})$

Since, $\Theta (i^{3})$ is greater than $\Theta (i^{2})$. Therefore final time complexity will be  $\Theta (i^{3})$.

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

So finally we can say the time complexity will be,

$\sum_{i=1}^{n}(i^3{})$ = $\Theta (n^{4})$.

---

@samarpita This was actually a very good question. Just one thing…

So now we will analyze, that how many times this (j%i==0) will satisfy.

→ It will satisfy when j=i,2*i,3*i….i*i.

→ Therefore inner for loop will run when j=i,2*i,3*i….i*i.

Here although for each $i$, $j$ runs as $1,2,.... i^2-1$, the inner ($k$ loop) will run only when $j = i, 2i, …, (i-1)*i$  because $j$ loop runs till $<i^2$ but satisfies when $(j\%i==0)$

So the exact final summation will be what @Argharupa Adhikary has received, i.e, $\sum_{i=0}^{n-1}(i*((i-1)*i)/2) =$ $(1/2)*\sum_{i=0}^{n-1}(i^3 - i^2) =  \Theta (n^{4})$ 

But since $i^3$ is dominating so it doesn’t matter much.

---

Abhrajyoti00

perfect 👌

This is indeed  a good question.

---

@Abhrajyoti00 that is not $i^{2}-1$ , that is i*(i-1) bcz everytime by i will get incremented.

---

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

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?