So here is how I tried to come up with the time complexity for the Sieve of Erast. According to Wikipedia it is $O(n \; \text{log} \;\text{log}\;n)$.

I got $O(n \; \text{ln}(\sqrt{n}))$

Here is what I did:

The main part of the algo I used is this one here:

1: for i=2 to sqrt(n) do
2:     for j=i to n/i do
3:         A[i*j] := False   

The part that seems to be dominating factor for the cost is line 2. I did the following.

Observe that

if $i=2$, then the loop condition is $j=2 \; to \; \frac{n}{2}$.

if $i=3$, then the loop condition is $j=3 \; to \; \frac{n}{2}$.

And then we write this more compactly as:

$$\sum_{i=2}^{\sqrt{n}}{\frac{n}{i}-i} $$

And then we do a bunch of simplications: $$= \sum_{i=2}^{\sqrt{n}}{\frac{n}{i}}-\sum_{i=2}^{\sqrt{n}}{i} $$ $$= n\sum_{i=2}^{\sqrt{n}}{\frac{1}{i}}-\sum_{i=2}^{\sqrt{n}}{i} $$

And then we pretend that $i=2$ is $i=1$ and use closed formulas (harmonic & arithmetic series):

$$=n \cdot \; \text{ln}(\sqrt{n}) -\frac{\sqrt{n}(\sqrt{n}+1)}{2} $$

And now I'm doing something I'm unsure about, let's say $\frac{\sqrt{n}(\sqrt{n}+1)}{2} \approx n$

So we get:

$$=n \cdot \; \text{ln}(\sqrt{n}) -n$$

This simplification was a bit too powerful because $n$ grows apparently much faster than the other term, so the whole thing becomes negative. So I just dropped $n$ completely.

This leaves me with:

$$n \cdot \; \text{ln}(\sqrt{n}) $$

And thus I'd say the time complexity of the Sieve of Eratosthenes $O(n \cdot \; \text{ln}(\sqrt{n}) )$.

I do feel like I broke some rules here and there, hence I'm asking. What I did notice is that the harmonic series is indeed part of the algo, so I think I was on the right track to some extend. Is this correct or does it violate some rule?

  • 4
    $\begingroup$ you can skip the inner loop if A[i] = False That will save you some time and you didn't account for that from what I could see $\endgroup$ Commented Jun 11 at 8:40
  • 1
    $\begingroup$ You are not wrong since $O(n\log\log n) \subset O(n\log \sqrt{n})$. You are simply overestimating. $\endgroup$
    – codeR
    Commented Jun 11 at 9:04
  • $\begingroup$ @codeR Yeah, goal was to find an accurate enough upper bound without becoming too mathy. The only thing which felt 'illegal' was simplifying $\frac{\sqrt{n}(\sqrt{n}+1)}{2}$ to just $n$ and then realizing the whole thing didn't work because $n$ grew faster, so I just dropped $n$. Was that the right thing to do or what is the approach I should take when I realize that thing I get goes negative? $\endgroup$
    – Yuirike
    Commented Jun 11 at 9:30
  • 4
    $\begingroup$ Note that $\ln\sqrt n=\frac12\ln n$, hence there is no point in writing $O(n\ln\sqrt n)$, it’s the same as $O(n\log n)$. But anyway, your computation is right. The only way to get down to $O(n\log\log n)$ is to do the inner loop only for $i$ such that A[i] == true (i.e., when $i$ is prime) as per ratchet freak’s comment, and use a bit of number theory: if $p$ runs over primes only, then $\sum_{p\le n}\frac1p$ is $O(\log\log n)$ rather than $O(\log n)$ (this is a weak version of en.wikipedia.org/wiki/Mertens%27_theorems#Second_theorem). $\endgroup$ Commented Jun 11 at 10:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.