GATE Overflow | Algorithms | Test 1 | Question: 3

Question

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++;

• A. $\Theta(1)$
• B. $\Theta(n)$
• C. $\Theta \left(n^2\right)$
• D. $\Theta\left(n^3\right)$

Comments

 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. 

---

@ Debashish

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

Answer 1

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

Comments

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)

Answer 2

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