Thread: 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(log₂ 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