1
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.