Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: O(log n): a simple question for Logarithm in Data structures & Algo

  1. #1
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

    Default O(log n): a simple question for Logarithm in Data structures & Algo

    regardless of my knowledge at the moment, but somehow I pretty much getting the ideas of O nations, when you see an O(log n), or Similar

    does it Always imply that the logarithm being used is Base-2? so when I see O(log N) it means O(log2 N)?


  2. #2
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: O(log n): a simple question for Logarithm in Data structures & Algo

    Quote Originally Posted by chronoz13 View Post
    ...
    does it Always imply that the logarithm being used is Base-2? so when I see O(log N) it means O(log2 N)?
    The log of a number to base A is equal to a constant times the log of that same number to base B, so the base is irrelevant as far as the use of Big-O notation is concerned.

    Generally speaking, the Big-O formulas that we see are most useful as an indication of growth rate with size of N, and don't actually measure the amount of memory or time (number of operations) required to reach a solution. I mean, generally speaking, if you had a way of arriving at an actual count and the actual value is important, you wouldn't use a Big-O expression; you would just write the formula for the count.

    Bottom line (from Big O Notation - Wikipedia):
    "the function g(x) appearing within the O(...) is typically chosen to be as simple as possible, omitting constant factors and lower order terms"

    Reference: Converting Logs to Another Base


    </begin Post-bottom-line comment> (pretty much irrelevant to the above considerations):
    Generally speaking, when mathematicians write an expression involving logarithms and they don't state the base, natural log (base e) is implicit.
    </end Post-bottom-line comment>


    Cheers!

    Z
    Last edited by Zaphod_b; September 7th, 2012 at 09:56 AM.

  3. The Following User Says Thank You to Zaphod_b For This Useful Post:

    chronoz13 (September 7th, 2012)

Similar Threads

  1. [SOLVED] Data Structures: Symbolic Algebra with Trees
    By Staticity in forum What's Wrong With My Code?
    Replies: 2
    Last Post: August 20th, 2012, 01:42 AM
  2. Replies: 0
    Last Post: November 6th, 2011, 03:55 PM
  3. Simple Data Base.
    By Reese in forum The Cafe
    Replies: 14
    Last Post: August 2nd, 2010, 02:23 PM
  4. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM
  5. not so simple, simple swing question box
    By wolfgar in forum AWT / Java Swing
    Replies: 2
    Last Post: November 20th, 2009, 03:47 AM