O(log_2(n)) = O(log_10(n))?

Question

Is it true to say that an algorithm that is in O(log_2(n)) is also in O(log_10(n))? I would say yes since log_2(n) = log_10(n)/log_10(2) and 1/log_10(2) is a constant.

In that case, if we consider a d-ary heap where the heapify operation depends of the height of the tree, why all the documents I have read specify the log radix in the complexity whereas d does not depends of the input size?

Answer 1

You are correct. The base of the logarithm can be ignored when talking about asymptotic behavior and the proof is exactly what you have provided.

I believe the papers you mention include the base for better clarity (although apparently it can be confusing too).

Answer 2

When considering big O notation ,

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

The base of any logarithm can be changed from a to b(both constant wrt. n) .

O(log₁₀(n)) is the same as O(log₂(n)), O(ln(n)), etc.