Thread: Big-O Notation Problem

Hm ok, I see that now. But how does this lead me to finding the Big-O notation? I thought usually this type of thing ends up in a summation formula that you multiply out and find the largest degree, but I don't see this happening. What does your notation mean? Is that supposed to be summation?

Ok wow, I've never seen a summation like that before. I don't know how to figure out this big-o stuff. Is that summation inside summation? Ugh this is confusing.

Hm, assuming you want me to expand that I get this http://hausheer.osola.com/latex2png/...0/0/result.png

So my Big-O is O(n^2) ?

Originally Posted by Sentral

Ok wow, I've never seen a summation like that before. I don't know how to figure out this big-o stuff. Is that summation inside summation? Ugh this is confusing.

Hm, assuming you want me to expand that I get this http://hausheer.osola.com/latex2png/...0/0/result.png

So my Big-O is O(n^2) ?

So by definition you cannot have i or j in your answer, since they're the variables of summation. Look at it: the first summation is

Code:

$\sum_{j=1}^{i} ji = i\sum_{j=1}^{i} j = i((i^2+i)/2) = (i^3+i^2)/2$.

Now that gets summed as i goes from one to n.

Edit: Or if you want it to look a little better:

Code:

$\sum_{j=1}^{i} ji = i\sum_{j=1}^{i} j = i\frac{i^2+i}{2} = \frac{i^3+i^2}{2}$.

Ok, I finally think I got it. This is my final answer.

Code:

(1/8)*n^4+(5/12)*n^3+(3/8)*n^2+(1/12)*n

O(n^4)