Please explain time complexity for all loops

#1
#2

Hello Nikhil, so let’s see the loops step by step.
The outer i loop is going from 0 to n.
And the inner j loop is from i to i*i
And then if j%i == 0 then from 0 to j

Now see for a particular value of i we are running j loop i to ii times
we can say that it is taking ii - i operations for that and for checking the condition that j%i == 0 then we can say that for particular i we can have i nos. of such values of j such that j%i == 0, as we can say that when
j = 1i,2i,3i,4i,(i-1)i so in total we have i such values of j so for some i then no. of total operations that the 3rd loop (kth variable loop) is doing are,
0 to i,0 to 2i,0 to 3i … 0 to (i-1)i as j can take these values.
so we can say that for a particular i the total no. of operations that the kth loop will do,
i+2i+3i+4i…(i-1)i so we can take i common then we will left with , i * (1+2+3+4…i-1) so overall it will be i[(i(i-1))/2] this is i * sum of elements till i-1

So Nikhil, till here we have the total no. of operations of j loop and k loop for particular i.
We can say that j loop will execute ii-i times and k th loop will execute i[(i*(i-1))/2].
So the overall formula turns out to be
summation of values from i = 0 to n,
ii-i + i[(i*(i-1))/2]
simplifying the loop
(i^3) + (i^2)/2 - i
so, here you will see that i^3 is the dominating factor among all of them
so, we can say that
for i = 0 to n:
i^3 (operations approximately)

now 0^3 + 1^3 + 2^3…(n-1)^3 we now the formula for summation of cubes of n natural nos.
[(n*(n+1))/2]^2 so from here we can say that O(n^4) is the time complexity of all the loops.

I hope it is clear to you. In case it is clear to you pls mark it as resolve and provide the rating as well as feedback so that we can improve ourselves.
In case there is still some confusion pls let me know, I will surely try to help you out.
Thanks :slight_smile:
Happy Coding !!

#3

but in the ans pdf n^5 is ans and how can j be i,2i ,3i it is increasig linearly

#4

and what is the explanation for n^5 ?? as j is going from i to ii so and by i,2i,3i i am saying that these are the values of j where it hits the kth loop. I know it is linear. but at i it will run the kth loop then i+1 it won’t run then i+2… 2i-1 won’t run but when j = 2*i then the kth loop will run again

#5

void function(int n)
{
int count = 0;
//executes O(n) times
for (int i=0; i<n; i++)
//Executes 0(n^2) times
for (int j=i; j< ii; j++)
if (j%i == 0)
{
//executes O(n^2) times
for (int k=0; k<j; k++)
System.out.println("");
}
}

#6

There is only this much explanation ??

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.