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

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

1. ## 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. ## Re: O(log n): a simple question for Logarithm in Data structures & Algo

Originally Posted by chronoz13
...
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

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

chronoz13 (September 7th, 2012)