I've found plenty of sources claiming that the time complexity of the prime sieving algorithm Sieve of Eratosthenes is $O(n\log(\log n))$ where $n$ is the input. However, is this $\log_{10}$ or $\ln$? I assume it's $\ln$ but according to some notational conventions, just $\log$ refers to $\log_{10}$ and I can't find a source that clarifies this problem.
Does anyone know?
EDIT: I know that in a case where you have only one logarithm, you can scale between different bases using constants. However, this is not true when you have several nested logarithms. I.e. $\log_{10}(\log_{10} n)/\ln(\ln n))$ does not equal $\log_{10}(\log_{10} (n+1))/\ln(\ln (n+1)))$. Because of this, the logarithmic base does matter here. (I think, correct me if I'm wrong).
Answer
Big $O$ complexity in terms of nested logarithms is base independent for the same reason it is in the case of single logarithms. For example, $\log_{10} x = c \log_2 x$ for the constant $c=\log_{10} 2$, as you have noted.
Likewise, using a specific example, $\log_{10} \log_{10} x = d \log_2 \log_2 x$ for some $d$ that approaches (but does not equal) $\log_{10} 2$. This is because $\log_{10} \log_{10} x = \log_{10}( c \log_2 x ) = \log_{10} c + \log_{10} \log_2 x = \log_{10} c + c \log_2 \log_2 x$. The factor by which the $c$ in the second term is multiplied, $\log_2 \log_2 x$, approaches infinity, so $c$ can be replaced with a slightly larger $d$, and eventually that will increase the value of the second term enough to account for the constant added to it, $\log_{10} c$.
For this reason, most logarithmic expressions (but not all) that typically show up in big $O$ notation are base independent, so no base need be specified.
That being said, if no base is specified, and there is no obvious reason it should be $10$ or something else, you can assume a base of $e$. It is on the author if that assumption is false when no other base was specified.
No comments:
Post a Comment