# Big-O Notation Problem

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 09-13-2009
Sentral
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?
• 09-13-2009
tabstop
Quote:

Originally Posted by Sentral
Is that supposed to be summation?

Since that's what it says, I'm going to say "yes". (Edit: Thanks to David Hausheer's LaTeX2PNG.)
• 09-13-2009
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) ?
• 09-13-2009
tabstop
Well, once you get to page ten of the book, it's amazing what you see. But just like everything else you work it from the inside to the outside.
• 09-13-2009
tabstop
Quote:

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}$.
• 09-13-2009
Sentral
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)
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12