1
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ Since $\log_ab={\ln b\over\ln a}$, the only difference is scaling by a constant, which does not appear in an asymptotic order statement. $\endgroup$ – abiessu Apr 5 '16 at 13:18
  • 3
    $\begingroup$ In the realm of asymptotic notation, it doesn't matter. Since you can change the base of any log with just multiplying by a constant, it won't matter what base the log is. But that complexity is kind of misleading since it doesn't account for the complexity with regard to input size. If you take this into account it is actually an exponential time algorithm. $\endgroup$ – ultrainstinct Apr 5 '16 at 13:19
0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

In this particular case, the base doesn't matter.

$$n\log_b(\log_b(n))=n\frac{\ln\left(\dfrac{\ln(n)}{\ln(b)}\right)}{\ln(b)}=n\frac{\ln(\ln(n))-\ln(\ln(b))}{\ln(b)}=O(n\ln(\ln(n)))$$ as the second term is of a lower order.

$\endgroup$
0
$\begingroup$

With the Sieve of Eratosthenes, $\log$ refers to $\ln$ and is due to the nature of the sieve and its relationship to the Prime number theorem $\pi(N) \sim N/\ln N$. (Computational analysis from wikipedia)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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