Bound for a function

[arcticm]

Hey everybody!
Really need some help cause I'm lost!
I need to find an asymptotically tight bound (theta) for this sum
http://img231.imageshack.us/img231/1606/32830911.jpg
, and I know u can't bound a sum, so I can't figure out a way to do it!! I'd REALLY appreciate if someone could explain to me (in the most simple way possible) what I need to do in a situation where I have a sum to bound)
THANK YOU!!!!

[Zachm]

A sum is just a different name for a function where the variable is the upper bound of the sum (the number above the sigma).
You can show that a function with a sum in it is asymptotically bounded by another function in exactly the same fashion you would for any regular function.

Showing that a specific Theta bound applies is equivalent to showing that both Big-Oh and Omega bounds apply (with a given bounding function).

You should probably start with some intuition - try to evaluate what the bound will be and then prove it is so. My hunch is that it's at least O(N^3) since you sum N times something that is at most N^2. Now we can try to show that N^3 also applies for the lower bound(Omega).

In your sum function, the input variable is N (the big N above the sigma).

Let's start with Big-Oh:

Sum{1..N} [ n*(n-1) / 2 ]  <= Sum{1..N} [ n*(n-1) ] <= Sum{1..N} [n^2] <= N * N^2 = N^3 
Therefore:
Sum{1..N} [ n*(n-1) / 2 ] = O(N^3)

As for Omega, you can think for yourself, I can give you a small hint:
what would happen if the sum lower bound(the number below the sigma) was something like N/2 and not 1 ?, that is you have a function that looks like this:

Sum{N/2 .. N} [ n*(n-1) / 2 ]

Obviously the original sum function is lower bounded by the new function I just described. Try to show that it is Omega(N^3).

Regards,
Zachm