Big O notation Log Base 2 or Log Base 10
This question already has an answer here:
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(log2X) = O(log10X)
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.
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.
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))
上一篇: 在一个B中键