recategorized by
866 views
8 votes
8 votes

For the following program fragment, the running time is given by

sum = 0; 
for(i = 1; i< n ; i++) 
    for(j = 1; j<i; j++) 
        if(i < j == 0) 
            for(k = 0; k<j; k++) 
                sum++;
  1. $\Theta(1)$
  2. $\Theta(n)$
  3. $\Theta \left(n^2\right)$
  4. $\Theta\left(n^3\right)$
recategorized by

2 Answers

Best answer
13 votes
13 votes
  1.  sum = 0;
  2.         for(i = 1; i< n ; i++)
  3.                for(j = 1; j<i; j++)
  4.                    if(i < j == 0)
  5.                         for(k = 0; k<j; k++)
  6.                                 sum++;


    Just check condition in line no 3 and 4. Once condition in line 3 satisfy this makes if condition false.
    Line no 4 is redundant actually.

     
  7.  sum = 0;
  8.         for(i = 1; i< n ; i++)
  9.                for(j = 1; j<i; j++)
  10.                         for(k = 0; k<j; k++)
  11.                                 sum++;
    Time complexity : 
    T(n) = $\sum_{i=1}^{n-1}$ $\sum_{j=1}^{i-1}$ $\sum_{k=0}^{j-1}$ 1
           = $\sum_{i=1}^{n-1}$ $\sum_{j=1}^{i-1}$ j
           = $\sum_{i=1}^{n-1}$ i(i-1)/2
           = { $\sum_{i=1}^{n-1}$ i^2 - $\sum_{i=1}^{n-1}$ i }/2
           =  { (n-1)n(2n-1)/6 - n(n-1)/2 }/2
           = { n(n-1)(n-2)/6}
           = Ɵ(n^3)

    Time complexity is Ɵ(n^3).
selected by
0 votes
0 votes

for(i = 1; i< n ; i++) //O(n)

for(j = 1; j<i; j++) //O(i) = O(n)

if(i < j == 0) // Means "i < j is False?" which is true for every instance. So, proceed.

for(k = 0; k<j; k++) // O(j) = O(n)

sum++;

Hence, $O(n^3)$

The if-condition will never be false, so the best case would be $\Omega (n^3)$. Hence, $\Theta (n^3)$

 

Option D

Answer:

Related questions

2 votes
2 votes
1 answer
2
Bikram asked Oct 4, 2016
327 views
The Matrix Chain-Product dynamic programming Algorithm runs in _______linear timeexponential timequadratic timecubic time
3 votes
3 votes
1 answer
4
Bikram asked Oct 4, 2016
499 views
Let we have 3 steps of an arbitrary program fragment whose running times are $O(n^2), \: O(n^3)$ and $O(n\log n)$, then the running time of whole program is$O(n^3)$$\Omeg...