Is Big O(logn) log base e?

Question

For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarithm? Sorry for the simple question but I've always had trouble distinguishing between the different implied logarithms.

Answer 1

Big O notation is not affected by logarithmic base, because all logarithms in different bases are related by a constant factor, O(ln n) is equivalent to O(log n).

Answer 2

Once expressed in big-O() notation, both are correct. However, during the derivation of the O() polynomial, in the case of binary search, only log₂ is correct. I assume this distinction was the intuitive inspiration for your question to begin with.

Also, as a matter of my opinion, writing O(log₂ N) is better for your example, because it better communicates the derivation of the algorithm's run-time.

In big-O() notation, constant factors are removed. Converting from one logarithm base to another involves multiplying by a constant factor.

So O(log N) is equivalent to O(log₂ N) due to a constant factor.

However, if you can easily typeset log₂ N in your answer, doing so is more pedagogical. In the case of binary tree searching, you are correct that log₂ N is introduced during the derivation of the big-O() runtime.

Before expressing the result as big-O() notation, the difference is very important. When deriving the polynomial to be communicated via big-O notation, it would be incorrect for this example to use a logarithm other than log₂ N, prior to applying the O()-notation. As soon as the polynomial is used to communicate a worst-case runtime via big-O() notation, it doesn't matter what logarithm is used.