# Thread: Complexity using big-Oh notation

1. ## Complexity using big-Oh notation

What is the worst case running time, in big-Oh notation, of the following program?

Code:
```int function(int n)
{
r=0;

for (i=1; i<n; i++)
for (j=i+1; j<n+1; j++)
for (k=1; k<=j; k++)
r++;
return r;

return 0;
}```

2. I feel confident that this is O(n! n^n e^n). You can probably come up with a sharper estimate, though, if you try.

(I.E. and in other words: show some effort and we will look more kindly upon the question.)

3. Originally Posted by tabstop
I feel confident that this is O(n! n^n e^n). You can probably come up with a sharper estimate, though, if you try.

(I.E. and in other words: show some effort and we will look more kindly upon the question.)
I''ve tried to calculate it...

4. If the result was O(n^2), and using the fact that the outer loop goes from 1 to n, that would suggest that the inner two loops together execute in O(n). Does that seem possible?

5. Originally Posted by tabstop
If the result was O(n^2), and using the fact that the outer loop goes from 1 to n, that would suggest that the inner two loops together execute in O(n). Does that seem possible?
I took it step by step
for i=1
first loop o(1), second o(n-1), third o(2)*o(2)*...*o(n) ---> that is o(n*n!)
for i=2
first loop o(1), second o(n-2), third o(3)*...*o(n)
and so on

for i=n-1
first loop o(1) second o(1), third o(n)