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

• September 7th, 2012, 04:12 AM
chronoz13
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)?
• September 7th, 2012, 08:20 AM
Zaphod_b
Re: O(log n): a simple question for Logarithm in Data structures & Algo
Quote:

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