in Algorithms edited by
2,351 views
1 vote
1 vote

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.

in Algorithms edited by
2.4k views

1 comment

Answer would be $O(n^4)$
0
0

2 Answers

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

selected by
by

1 comment

Thank you, Answer was given O(n^5) hence I got confused earlier, your explanation helps.
0
0
4 votes
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})$

edited by
by

1 comment

Amazing explanation !!!

0
0

Related questions

1 vote
1 vote
0 answers
3