0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Raphael Oct 25 '17 at 21:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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.

$\endgroup$
  • $\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 '17 at 21:41

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