Results 1 to 14 of 14
  1. #1
    dougie1809 is offline Senior Member
    Join Date
    Nov 2011
    Posts
    116
    Rep Power
    0

    Default The Big O Notation

    Hi,

    How do you calculate the Big O worst cast scenario for a merge sorting algorithm?
    The formula is O(n log n) and say if you have the value of 'n' to be 14.

    I really can't get my head around it?

    Thanks

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,963
    Rep Power
    8

    Default Re: The Big O Notation

    What is your actual question? You have already supplied the Big-O runtime of mergesort. Are you asking how to get O(n lgn) in the first place, or are you asking how to plug 14 in for n?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    dougie1809 is offline Senior Member
    Join Date
    Nov 2011
    Posts
    116
    Rep Power
    0

    Default Re: The Big O Notation

    Yes how to plug 14 in for n, and to get a result of the amount of steps it took for that algorithm? (But not in code, Just in theory)
    Thanks

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,530
    Blog Entries
    7
    Rep Power
    20

    Default Re: The Big O Notation

    Also note that O(f(n)) == O(c*f(n)) where c is any constant, so if you plug in a (small) value for n, the answer by itself doesn't tell you anything.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    dougie1809 is offline Senior Member
    Join Date
    Nov 2011
    Posts
    116
    Rep Power
    0

    Default Re: The Big O Notation

    Is that another formula for merge or something? I mean can I not just use the basic O(n log n) merge formula to plug in the value?
    Thanks

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,530
    Blog Entries
    7
    Rep Power
    20

    Default Re: The Big O Notation

    Quote Originally Posted by dougie1809 View Post
    Is that another formula for merge or something? I mean can I not just use the basic O(n log n) merge formula to plug in the value?
    Thanks
    No and no, you can't just plug in a value and expect something reasonable from the answer.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    dougie1809 is offline Senior Member
    Join Date
    Nov 2011
    Posts
    116
    Rep Power
    0

    Default Re: The Big O Notation

    Ok, what would be the easiest way to calculate the Big O if you have 14 data records that you want to sort in theory? That's really all my problem?

    Thanks

  8. #8
    dougie1809 is offline Senior Member
    Join Date
    Nov 2011
    Posts
    116
    Rep Power
    0

    Default Re: The Big O Notation

    The bubble sort is an O(n^2) formula, so if the value of n is 14, then :

    O(n^2)
    = 14^2
    =196

    So therefore is took the bubble sort 196 steps to complete the sort.

    Now I am sure it would be as simple to do a calculation for the merge O(n log n)?
    I just can't plot them in?
    Any suggestions?

    Thanks
    Last edited by dougie1809; 04-23-2012 at 09:02 PM.

  9. #9
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,530
    Blog Entries
    7
    Rep Power
    20

    Default Re: The Big O Notation

    Quote Originally Posted by dougie1809 View Post
    Ok, what would be the easiest way to calculate the Big O if you have 14 data records that you want to sort in theory? That's really all my problem?
    You seem to want to count the number of elementary operations needed by your sorting algorithm; increment a simple counter each time your algorithm performs one of those elementary operations. A compare or a swap or a single append to a list etc. count as simple operations.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    dougie1809 is offline Senior Member
    Join Date
    Nov 2011
    Posts
    116
    Rep Power
    0

    Default Re: The Big O Notation

    Oh yes, I do understand how it may be written in code, but I'd like to be able to write it down as an equation i.e.

    : O(n log n)
    = 14 log(14)
    = ??

    Id like to calculate in that kind of sense, the same way the bubble sort O(n^2) can be calculated?

    Thanks

  11. #11
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,530
    Blog Entries
    7
    Rep Power
    20

    Default Re: The Big O Notation

    Well, 14*log(14) == 36.9468026146, but that number doesn't say much (see my first reply in this thread).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    dougie1809 is offline Senior Member
    Join Date
    Nov 2011
    Posts
    116
    Rep Power
    0

    Default Re: The Big O Notation

    Ah ok, that looks promising. Now how did you calculate 36.9468026146? I mean how is log(14) calculated?

    Thanks

  13. #13
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,530
    Blog Entries
    7
    Rep Power
    20

    Default Re: The Big O Notation

    Quote Originally Posted by dougie1809 View Post
    Ah ok, that looks promising. Now how did you calculate 36.9468026146? I mean how is log(14) calculated?
    I pressed the 'ln' key on my calculator; if you want the base 2 log, note that a-log(x) == b-log(x)/b-log(a). So 2-log(14) == log(14)/log(2) == 3.8073549221. But again, those numbers don't say much in big-Oh computations (that's why a 'ln' is as good as any base log).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  14. #14
    dougie1809 is offline Senior Member
    Join Date
    Nov 2011
    Posts
    116
    Rep Power
    0

    Default Re: The Big O Notation

    Ok, thanks for you help, I understand how this could get complicated when dealing with larger data set. But thanks again.

Similar Threads

  1. Big-O Notation
    By kraigballa in forum New To Java
    Replies: 9
    Last Post: 02-23-2012, 02:17 AM
  2. += notation
    By sehudson in forum New To Java
    Replies: 2
    Last Post: 03-11-2011, 04:51 AM
  3. Big O notation
    By simorgh in forum Advanced Java
    Replies: 18
    Last Post: 07-10-2010, 03:26 PM
  4. Big O notation
    By vendetta in forum New To Java
    Replies: 6
    Last Post: 01-08-2010, 07:47 PM
  5. Big O Notation
    By dsym@comcast.net in forum New To Java
    Replies: 1
    Last Post: 02-21-2009, 06:02 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
  •