what is the time complexity for the below question ?

Question

For the below code :
 

foo()
{
  for(i=1;i<=n;i++)
   {
     for(j=0;j<i;j++)
      {
        for(k=0;k<j;k++)
        c++;
      }
   }
}

 

Here k is executing j-1 times j is executing i times and i is executing n^2 times, so first I am doing summation from

k=0 to k=j-1 over k , I am getting Order j^2, Now j is summed up from 0 to i, so I am getting order of i^3 , Now when I am doing summation of i from i=1 to n^2 , I am getting order of n^8 . But this is getting too large, I checked with an example, it is not matching,So please correct where I went wrong.

Comments

here i is executing only n times and order is $n^{3}$.

---

You might find this link interesting as well:

https://stackoverflow.com/questions/11094330/determining-the-big-o-runtimes-of-these-different-loops

Answer 1

The $i$ loop does not execute $n^{2}$ times but $n$ times

The time complexity of this function can be computed by solving the following Summation:

$\sum\limits_{i=1}^{n}\sum\limits_{j=0}^{i-1}\sum\limits_{k=0}^{j-1}1$

I am taking 1 as the constant  inside summation as it won't matter while computing time complexity in Big O notation

We know that : $\sum\limits_{k=0}^{j-1}1=j$  (summing 1 j times will be equal to j)

Now using this in our original summation we get:

$\sum\limits_{i=1}^{n}\sum\limits_{j=0}^{i-1}j$

Similarly solving for $\sum\limits_{j=0}^{i-1}j$ we get $\frac{i(i-1)}{2}$

using this result in above equation we get:

$\sum\limits_{i=1}^{n}\frac{i(i-1)}{2}$

Simplifying this to:

$\frac{1}{2}\sum\limits_{i=1}^{n}(i^{2}-i)$

Solving this we get the maximum order term in the form of $n^{3}$ in the result, Hence the running time complexity is $O(n^{3})$

Answer 2

is the answer O(n^3)..?