488 views

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

 if(i < j == 0)

if statement is true for all the j values in a single iteration of second loop.

Summing $O(k^2)$ for $n-1$ times with $k=1,2,3,4,...n-1$ gives total $\Theta (n^3)$ complexity.

Complexity should be O(n2). Plz chk my query below :(

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

In given question line 4 is redundant

after not considering line 4 in program, line 5 will execute or not..?
LINE 5,6 is in  the block of 4.???
value in variable sum ??

Is it O(n^3)

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