time-complexcity

Question

for(i=0;i<n;i++)

   for(j=0;j<i;j++)

      for(k=0;k<j;k++)

 

what is the time complexity of above psudo code?

explain.

Comments

It is

O( n^3 ).

---

first loop is executed for n times i=0,1....n-1

second loop is called for every value of i, so second loop runs for 0 iterations then 1 then 2, ...... and finally n-1

so in total 1+2+3+....+n-1 = (n-1)(n)/2 times

third loop runs for every value of j

so first when j=1, third loop runs once

when j=2, third loop runs for k=0 and k=1 so twice

And similarly when j= n-1 total n-1 loops

1+(1+2)+(1+2+3)+(1+2+3+4)+.....+(1+2+3+4....n-1)

=(n-1)(1) +(n-2)(2)+ (n-3)(3)+.......(1)(n-1)

=(n-1)(1) +(n-2)(2)+ (n-3)(3)+.......(n-(n-1))(n-1)

=[n+2n+3n+4n+5n+6n+.......(n-1)n]-[ 1²+2²+3²+4²+....(n-1)²]

=[n(1+2+3+4+5+6+.......(n-1)]-[ 1²+2²+3²+4²+....(n-1)²]

=n(n-1)(n)/2 - [1²+2²+3²+4²+....(n-1)²]

=[n(n-1)(n)/2] - [(n-1)*n*(2n-2+1)/6]

=(n³+n)/6

=$\Theta$(n³)

 

Answer 1

I think the answer is O(n^3)

Comments

Yes it is O(n^3)

---

Can you elobrate?