What are the time complexities of the following C codes?

Question

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 ?

Answer 1

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

There are a few points in what you presented you may need to make rigorous.

Answer 2

I think the first one is right but not for the right reason. The if triggers exactly once for each revolution of the outer loop.

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.