Big O notation Log Base 2 or Log Base 10 [duplicate]

Question

This question already has answers here:

Is Big O(logn) log base e? (7 answers)

Closed 8 years ago.

When articles/question state that the Big O running time of the algorithm is O(LogN) .

For example Quicksort has a Big O running time of O (LogN) where the it is Log base 10 but Height of binary tree is O(LogN+1) where it is Log base 2

Question

1)I am confused over whether is it Log base 10 or Log base 2 as different articles use different bases for their Logarithm .

2) Does it make a difference if its Log base 2 or Log base 10??

3)Can we assume it mean Log base 10 when we see O(LogN)???

Answer 1

I think it does not matter what is the base of the log as the relative complexity is the same irrespective of the base used.

So you can think of it as O(log₂X) = O(log₁₀X)

Also to mention that logarithms are related by some constant.

So

log₁₀(x) = log₂(x) / log₂(10)

So most of the time we generally disregard constants in complexity analysis, and hence we say that the base doesn't matter.

Also you may find that the base is considered to be 2 most of the time like in Merge Sort. The tree has a height of log₂ n, since the node has two branches.

1)I am confused over whether is it Log base 10 or Log base 2 as different articles use different bases for their Logarithm .

So as explained above this change of base doesn't matter.

2) Does it make a difference if its Log base 2 or Log base 10??

No it does not matter.

3)Can we assume it mean Log base 10 when we see O(LogN)???

Yes you can assume that provided you know the base conversion rule.

Answer 2

log₁₀(x) = log₂(x) / log₂(10) for all x. 1/log₂(10) is a constant multiplier and can be omitted from asymptotic analysis.

More generally, the base of any logarithm can be changed from a to b (both constant wrt. n) by dividing by logₐ(b), so you can freely switch between log bases greater than one: O(log₁₀(n)) is the same as O(log₂(n)), O(ln(n)), etc.

An example consequence of this is that B-trees don't beat balanced binary search trees asymptotically, even though they give higher log bases in analysis. The just have better constants.

Answer 3

In Big O notation, O(log(n)) is the same for all bases. This is due to logarithm base conversion:

log2(n) = log10(n)/log10(2)

1/log10(2) is just a constant multiplier factor, so O(log2(n)) is the same as O(log10(n))