Re: The computational complexity of the Sieve of Eratosthenes

Richard Heathfield wrote:
[...] The wikipedia page gives a
complexity of O((n log n)(log log n)) for the [Sieve of
Eratosthenes] algorithm. Where does this come from?

Without looking /too/ closely at it, I would guess that it has to do with
the fact that the number of primes less than n is, to a first
approximation, n / log n.

If pi(n) is O(n/log n), then O(sqrt(n*pi(n))) becomes
O(sqrt(n*n/log n)) = O(n/sqrt(log n)).

I still don't get where the O((n log n)(log log n)) is coming from.
.

Relevant Pages