Help finding Complexity in Big-O notation

[pandrade]

Homework Statement

I have found the complexity of an algorithm as the expression below. How can I find the complexity in big O notation for such expression? Or proved that it's bounded by $$n^3$$or $$n^4$$ ? Thank you!

Homework Equations

$$\sum_{j=3}^{n} \left[(j-1)[2(j-2)-1] + \sum_{i=2}^{j-2}(i) + <br /> \sum_{k=2}^{j-2}\left[k(j-(k+1))+\sum_{i=k}^{j-2}(i)\right]\right]$$

The Attempt at a Solution

I run 1000 numbers and apparently it is bounded by $$n^3$$.

 

[mfb]

First simplification step:
$$\sum_{j=3}^{n} \left[O(n)O(n) + O(n^2) + <br /> \sum_{k=2}^{j-2}\left[k(j-(k+1))+\sum_{i=k}^{j-2}(i)\right]\right]$$
To get O(n^3) I think you have to evaluate the innermost sum to cancel some parts of the k(j-(k+1)), but apart from that (or for an O(n^4)-boundary) you can always estimate those terms as bounded by n, with rules like O(n)O(n)=O(n^2) and so on.

 

[pandrade]

I see.
To be honest I would like to get a $$n^3$$ :-), but I see what you are saying.
I have plotted it against $$n^3$$ for $$n$$ from 1 to 10,000 and I guess I got carried away because it seemed to be asymptotically bounded, but of course, there's no guarantee, at all.
I will try to open the sum and see if it cancels out, as you suggested, if not, I'll consider $$n^4$$.
Thank you so much!

 

[mfb]

I don't think this is O(n^3).
I would expect O(n^4), and this is easy to show.