in Algorithms recategorized by
488 views
7 votes
7 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)$
in Algorithms recategorized by
by
488 views

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

5
5

@ Debashish

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

0
0

2 Answers

13 votes
13 votes
Best answer
  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

4 Comments

In given question line 4 is redundant

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

Is it O(n^3)
0
0
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