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$
2
  • 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
    Commented Apr 5, 2016 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$ Commented Apr 5, 2016 at 13:19

3 Answers 3

2
$\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$
1
$\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$
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .