Results 1 to 5 of 5
  1. #1
    kira137 is offline Member
    Join Date
    Oct 2009
    Posts
    14
    Rep Power
    0

    Default Big O notation question

    I was having trouble understanding big-O notation so I searched around websites.. then I came across this:

    /////////////Random Post//////////////////
    ...
    or (int j = 1; j < n; j *= 2)
    sum += j;

    is it also O(n)??

    ---------------------------------------
    this is what i was talking about in my last post:
    since the value of j is increasing by a multiple of 2 each time, in an ordered way, think of it as the formula: 2^p. This is more easily seen as a form of log(n), otherwise known as a loop which runs faster than n, in a logorithmic pattern.
    Therefore O(log(n))
    **As a note, if the question had been:
    for (int j = 1; j < n; j += 2) //notice the + instead of *
    sum += j;

    then it would be O(n), since the end result is running n/2 times, which is simply 1/2*n a co-efficient which is dropped, and results in O(n).
    /////////////////////////////////////////////

    I think I get the concept of ..say.. 3n^2+3n, then turn that into O(n^2).. and why other values doesn't matter and stuff..
    but what I don't get is, how they got the equation in the first place, by looking at code.

    like example from above
    Java Code:
    (int j = 1; j < n; j *= 2)
    sum += j;
    the post says 'look at this code as 2^p, therefore it is O(log(n)).

    I don't understand how he got 2^p from

    also with
    Java Code:
    for (int j = 1; j < n; j += 2) //notice the + instead of *
    sum += j;
    it says 'end result is running n/2 times, which is simply 1/2*n'

    how did he get 1/2 from?

    I hope you understood my question.. it bugs me not understanding Big-O Notation fully,,
    Thank you in advance!

  2. #2
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    7

    Default

    n/2 is a fraction. 1/2 * n/1 is n/2

    your question isn't an issue of understanding Big O it's with understanding fraction multiplication. You seem to have a decent handle on run time notation.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  3. #3
    kira137 is offline Member
    Join Date
    Oct 2009
    Posts
    14
    Rep Power
    0

    Default

    no, I didn't mean fraction multiplcation.
    What I don't understand is where they got the 1/2 from

  4. #4
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    7

    Default

    I believe it's because your counter is incrementing by 2 instead of 1. so to get from 1 to n would take half as much time.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  5. #5
    kira137 is offline Member
    Join Date
    Oct 2009
    Posts
    14
    Rep Power
    0

Similar Threads

  1. Question mark colon operator question
    By orchid in forum Advanced Java
    Replies: 9
    Last Post: 12-19-2010, 08:49 AM
  2. Reverse Polish notation with stacks confusion
    By jigglywiggly in forum New To Java
    Replies: 3
    Last Post: 10-05-2009, 07:40 PM
  3. Big O Notation
    By dsym@comcast.net in forum New To Java
    Replies: 1
    Last Post: 02-21-2009, 06:02 PM
  4. Postfix-Notation
    By little_polarbear in forum New To Java
    Replies: 9
    Last Post: 09-09-2008, 04:24 PM
  5. Big Oh Notation and Heaps
    By gibsonrocker800 in forum Advanced Java
    Replies: 8
    Last Post: 01-25-2008, 10:06 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •