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 [tex] n^3 [/tex]or [tex] n^4 [/tex] ? Thank you!

Homework Equations

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

The Attempt at a Solution

I run 1000 numbers and apparently it is bounded by [tex] n^3 [/tex].

 

[mfb]

First simplification step:
[tex] \sum_{j=3}^{n} \left[O(n)O(n) + O(n^2) +
\sum_{k=2}^{j-2}\left[k(j-(k+1))+\sum_{i=k}^{j-2}(i)\right]\right] [/tex]
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 [tex] n^3 [/tex] :-), but I see what you are saying.
I have plotted it against [tex] n^3 [/tex] for [tex] n [/tex] 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 [tex] n^4 [/tex].
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.

 

[rezeew]

In order to find the complexity in big O notation, we need to analyze the expression and determine its highest order term. In this case, we can see that the highest order term is n^3, as it is the term with the largest exponent. Therefore, the complexity in big O notation would be O(n^3).

To prove that the expression is bounded by n^3, we can use the definition of big O notation which states that a function f(n) is bounded by g(n) if there exists a constant c and a value n0 such that f(n) <= c*g(n) for all n>n0. In this case, we can set c=1 and n0=1, and we can see that for all values of n greater than 1, the expression given will always be less than or equal to n^3. Therefore, we can conclude that the expression is bounded by n^3.