-1
$\begingroup$

What is the asymptotic runtime of fthe ollowing piece of code in terms of number of updates to S in worst case.

Void foo( int n)  
{  

    int S = 0;  

   for ( i=1 ; i<= n ; i++)  
    {  

           for( j = 1 ; j<= i*i ; j++)  
               {  
                  if(j % i == 0)  
                     {  
                       for( k=1 ; k<=j ; k++)  
                       s++;  
                     }  
               }  
     }  
}   

My way :

  1. Outer for loop will execute 'n' time.

  2. Middle for loop will execute 'n^3' times. Because j is reaching to i*i.
    So if n =10 ,i will move from 1 to 10. j will execute 1*1 + 2*2 + 3*3 + ..... + 10*10. i.e. 1^2 + 2^2 + ... + n^2 = maximum term is n^3.

  3. Inner for loop will execute maximum 'n' times. Suppose n = 10 , and i reaches to 10 i.e. i = 10 , so j can reach 1 to 10 * 10. In this maximum 10 times i.e. n times 'if loop' condition will be fulfilled.

    so total n * n^3 * n = Theta ( n^5 )

But answer is given as Theta ( n^4 ) and explained in totally mathematical terms ( which I didnt get )

Did I make any mistake ?

$\endgroup$
0
$\begingroup$

You can get a better bound by taking into account the fact that the innermost loop only runs $1/i$ of the times. The number of times that the body of the $j$-loop is executed is $$ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \Theta(n^3), $$ as you notice correctly. The innermost loop is run whenever $j$ is a multiple of $i$, that is, for the values $ti$ for $t=1,\ldots,i$. Therefore the $k$-loop is executed this many times: $$ \sum_{i=1}^n \sum_{t=1}^i ti = \sum_{i=1}^n i \sum_{t=1}^i t = \sum_{i=1}^n i \frac{i(i+1)}{2} = \frac{n(n+1)(n+2)(3n+1)}{24} = \Theta(n^4).$$ In total, the running time is $\Theta(n^4)$. Note that there is no need to calculate the exact formula; for example, we could use the rough lower and upper bounds $$ \sum_{i=1}^n i \sum_{t=1}^i t \geq \sum_{i=n/2}^n (n/2) \sum_{t=n/4}^{n/2} (n/4) = n^4/64, \\ \sum_{i=1}^n i \sum_{t=1}^i t \leq \sum_{i=1}^n n \sum_{t=1}^n n = n^4, $$ which are good enough for our purposes.

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