2,351 views

Consider the following c fragment :

void DAA(n)
{
int i,j,k,x=0;
for (i=1 ; i <=n ; i++)
for (j=1 ; j <= i * i ; j++)
{
if ( j mod i == 0 )
for ( k = 1 ; k <= j ; k++)
x=x+10;
}
}

Find the time complexity of above code in terms of input size n.

### 1 comment

Answer would be $O(n^4)$

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

by

### 1 comment

Thank you, Answer was given O(n^5) hence I got confused earlier, your explanation helps.

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

by

### 1 comment

Amazing explanation !!!