# What are the time complexities of the following C codes?

## Code first :

sum = 0
for(i=1; i<=n; i++){
for(j=1; j<=i; j++){
if(j%i == 0){
for(k=1; k<=n; k++){
sum = sum + k;
}
}
}
}

Total no. of iterations in $j = 1+2+3+4+ \dots +n \\= \frac{n. (n+1)}{2} \\= \Theta(n^2)$ total no. of times $k$ loop iterates = $n\times n = \Theta(n^2)$

So, time complexity $= \Theta(n^2) + \Theta(n^2)$ $= (n^2).$

## Code second :

for(int i =0 ; i < =n ; i++) // runs n times
for(int j =1; j<= i * i; j++) // same reasoning as 1. n^2
if (j % i == 0)
for(int k = 0; k<j; k++) // runs n^2 times? <- same reasoning as above.
sum++;

Correct Answer$: n×n^2×n = O(n^4)$

Please check whether my solution is correct ?

For the first code, you are correct in observing that the inner-most for loop runs once every time the second for loop runs, as $j=0\mod i$ only when $j=i$, so the time complexity is $\Theta(n^2)$.
For the second code, observe that the inner-most for loop runs $i$ times every time the second for loop runs. Hence the inner-most loop runs $\Theta(n^2)$ times, and it mainly does $\Theta(n^2)$ operations, making the total time complexity $\Theta(n^4)$.
But for the second that "if" line removes all but 1 out of every $i$ of the $j$s. So the inner loop only runs approximately $1/n$ of the time. Should give us $O(n^3)$ instead.