Dark Mode

2,351 views

4 votes

Best answer

Answer would be $O(n^4)$

To understand this you have to understand this how many times this **condition (C1)**

if ( j mod i == 0 )

will be true.

Lets take i = 5, then max value of j will be 25, it means that C1 will be true 5 times (when j = 5,10,15,20,25).

Similarly take i = 7, then max value of j will be 49, this time C1 will be true 7 time (when j = 7,14,21,28,35,42,49).

It means that condition C1 will be true for $\frac{j^2}{i}$ times.

Hence inner loop run only $O(n)$ rimes.

Therefore we get time complexity of $O(n^4)$.

4 votes

let's suppose $i = k$ then second loop will run $k^{2}$ times.

for a moment let assume third loop never executes then for each iteration of $\large i$ second loop will take $\large k^{2}$ time.

But in a complete run of second loop sometimes third loop gets executed whenever that $\large if$ condition becomes $\large true$.

Well how many times that condition becomes true ? Lets see ..

assume $\large i = k$ :

if $\large i=k$ than $\large j = 1 , 2 , 3 , 4 , 5 ................k-1,k*1,k+1,k+2...k*2,k*2+1,k*2+2,....k*3...................k*k$

You can see here that for $\large j=1k,2k,3k,............k*k(=k^{2})$ condition $\large j \mod \ i == 0$ is true. So $\large k$ times.

Now third loop runs for $\large j=1k,2k,3k,............k*k(=k^{2})$ in a complete run inside second loop. So third loop execution time $\large 1k + 2k +3k + .............+k^{2}\\ =\frac{k^{2}*(k+1)}{2}$

This will add up to the remaining time of a run of second loop which is $\large k^{2} - k$.

Net time of second loop for each value of i = k

$\large \frac{k^{2}(k+1)}{2} + (k^{2} - k)\\ = \frac{k^{3} + 3k^{2} - k}{2}$

Total time

$\large \sum_{k=1}^{n} \frac{k^{3} + 3k^{2} - k}{2} = O(n^{4})$