Is Big O(logn) log base e?

math binary-tree complexity-theory big-o
BuckFilledPlatypus picture BuckFilledPlatypus · Oct 15, 2009 · Viewed 40.6k times · Source

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

Cade Roux picture Cade Roux · Oct 15, 2009

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).

enter image description here

Related questions

Number of binary search trees over n distinct elements

How many binary search trees can be constructed from n distinct elements? And how can we find a mathematically proved formula for it? Example: If we have 3 distinct elements, say 1, 2, 3, there are 5 binary search trees.

Read More
The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?

This has been bothering me for a while. I know that given N keys to arrange in the form of a binary search tree, the possible number of trees that can be created correspond to the Nth number from the …

Read More
How can I check for NaN values?

float('nan') results in Nan (not a number). But how do I check for it? Should be very easy, but I cannot find it.

Read More