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?

  • $\begingroup$ You can read this post $\endgroup$
    – fade2black
    Oct 25, 2017 at 17:11
  • $\begingroup$ Very interesting math ( I see it should not be included ), but what is the actual value? $\endgroup$ Oct 25, 2017 at 17:13
  • $\begingroup$ 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})$. $\endgroup$
    – fade2black
    Oct 25, 2017 at 17:17
  • $\begingroup$ I'm interested in the actual value. The math problem has been answered already in the post by fade2black. $\endgroup$ Oct 25, 2017 at 17:49
  • $\begingroup$ As David Richerby answered, its actual value depends on how you do analysis. $\endgroup$
    – fade2black
    Oct 25, 2017 at 17:55

1 Answer 1


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.

  • $\begingroup$ "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. $\endgroup$
    – Raphael
    Oct 25, 2017 at 21:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.