# In a Binary Search Tree what is the base of the log in this Big O notation [duplicate]

when discussing average time complexity as in this table.

O (log n)

I'm assuming it is 2 but wanted to verify. Also is it always 2 for these data structures?

I'm in the opinion that the base of the log is not considered a constant so it should be included in the Big O notation.

Whether or not is should be included. What is the actual value?

• You can read this post – fade2black Oct 25 '17 at 17:11
• Very interesting math ( I see it should not be included ), but what is the actual value? – stack overflow Oct 25 '17 at 17:13
• The base is not important as long as you deal with Big-O notation. For any two bases $a$ and $b$, $\log_b{n} \in O(\log_a{n})$ and $\log_a{n} \in O(\log_b{n})$. – fade2black Oct 25 '17 at 17:17
• I'm interested in the actual value. The math problem has been answered already in the post by fade2black. – stack overflow Oct 25 '17 at 17:49
• As David Richerby answered, its actual value depends on how you do analysis. – fade2black Oct 25 '17 at 17:55

## 1 Answer

It doesn't matter what the base of the logarithm is. $\log_a x = (\log_bx)/\log_b a$ so changing from one (constant) base to another just introduces a constant factor. Big-$O$ and related concepts don't care about constant factors.

The base of the log is absolutely a constant: the base used for the calculations might depend on the whim (or, more likely, convenience) of the person who did the analysis but it certainly doesn't depend on the input.

• "The base of the log is absolutely a constant" -- one can certainly come up with algorithms for which this is not the case, but usually it is so. – Raphael Oct 25 '17 at 21:41