Complexity using big-Oh notation

[Delia]

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

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;
}

[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.)

[Delia]

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...
My answer was O(n^2)

[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?

[Delia]

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)

And then we add them.
Is this how it works?

[tabstop]

The first loop isn't O(1), it's O(j) -- more specifically, it's exactly j. So that means your second loop, you need to add up j as j goes from i+1 to n+1 (you should hopefully have a formula for that). Then that value gets added as i goes from 1 to n.

[brewbuck]

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.

How do you figure? No loop executes more than n times, so it can't be bigger than O(n^3)

[tabstop]

How do you figure? No loop executes more than n times, so it can't be bigger than O(n^3)

O is just an upper bound, so any algorithm that is O(n^3) is also O(n^4), and ..., and O(anything really big). (It's not helpful, but it's true.)