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

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?