# Is this how I could come up with the time complexity for the Sieve of Eratosthenes?

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?

• 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 Commented Jun 11 at 8:40
• You are not wrong since $O(n\log\log n) \subset O(n\log \sqrt{n})$. You are simply overestimating. Commented Jun 11 at 9:04
• @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? Commented Jun 11 at 9:30
• 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). Commented Jun 11 at 10:39