Big-O Notation Problem

This is a discussion on Big-O Notation Problem within the General Discussions forums, part of the Community Boards category; Hm ok, I see that now. But how does this lead me to finding the Big-O notation? I thought usually ...

  1. #16
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    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?
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  2. #17
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Sentral View Post
    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.)
    Attached Images Attached Images  

  3. #18
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    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) ?
    Last edited by Sentral; 09-13-2009 at 05:06 PM.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  4. #19
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  5. #20
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Sentral View Post
    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}$.
    Last edited by tabstop; 09-13-2009 at 05:24 PM.

  6. #21
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    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)
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  2. I have big problem with encryption by ASCII
    By LINUX in forum C++ Programming
    Replies: 7
    Last Post: 04-29-2007, 12:46 PM
  3. polish notation calc problem
    By deedlit in forum C Programming
    Replies: 6
    Last Post: 06-14-2004, 10:17 PM
  4. Need Big Solution For Small Problem
    By GrNxxDaY in forum C++ Programming
    Replies: 8
    Last Post: 08-01-2002, 03:23 AM
  5. problem with pointer notation in for-loop
    By sballew in forum C Programming
    Replies: 5
    Last Post: 09-30-2001, 06:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21