Question: What would be the complexity of the following code? would it be N^2\*log(n)?

```
for (int m = 1; m <= n; m++)
{
   for (int k = m; k >= 1; k--)
   {
      for (int i = 1; i <= k; i++)
      {
          //do something here
      }
    }
 }

```

Any help is appreciated thanks.

Answer: 
How long does the innermost loop take given the running time of the body of the loop is `O(C)`? `O(C*k)`

How long does the second loop take? `O(C*(1+2+3+...+m)) = O(C*m²)`

How long does the whole code snipplet take? `O(C*(1²+2²+3²+...+n²)) = O(C*n³)`

For summing polynomials see [Faulhaber's formula](http://en.wikipedia.org/wiki/Faulhaber's_formula).
The first loop is executed n times.
The second loop executes n/2 times.
The third loop is executed k/2 times, which equals to n/4 times.

This gives you a O(n^3) complexity.

Empirical test:

```
#include <iostream>

using namespace std;

int main () {
    int n = 1000;

    long first = 0, second = 0, third = 0;

    for (int m = 1; m <= n; m++)
    {
        first++;
       for (int k = m; k >= 1; k--)
       {

          second++;
          for (int i = 1; i <= k; i++)
          {
              third++;
          }
        }
     }

    cout << first << " " << second << " " << third << endl;

    return 0;
}

```

result:

```
1000 500500 167167000

```