The computational complexity of the Sieve of Eratosthenes

Calculating the computational complexity of the Sieve of Eratosthenes
algorithm is surprisingly difficult.

After reading the algorithm the very first intuition is that it's an
O(n^2) algorithm: For each number the table is traversed and multiples
of that number are marked as non-prime. Sounds like typical O(n^2) behavior.

However, on closer examination one discovers that's actually not true:
The inner loop can be started from the square of the number, not the
number itself. This would suggest that the algorithm is actually
O(n*sqrt(n)).

Yet, on even closer examination one discovers that the inner loop is
actually not executed for each number, but only for primes. The amount
of primes is smaller than O(n). Thus a more accurate estimation would be
O(n*sqrt(pi(n))), where pi is the prime counting function.

And still something is off: The outer loop actually doesn't go through
all the numbers: It stops after sqrt(n) numbers have been traversed.
Thus an even more accurate estimate is O(sqrt(n)*sqrt(pi(n))), or in
other words, O(sqrt(n*pi(n))).

But here's were my skills fall short. The wikipedia page gives a
complexity of O((n log n)(log log n)) for the algorithm. Where does this
come from?
.

Relevant Pages

  • Re: Comparing lists
    ... >> of computational complexity in terms of Big-Oh ... > algorithm will be, or how one algorithm compares to another. ... > complex set up for the merge-sort variant used for larger lists. ... > As for sets, they are based on dicts, which are effectively hash tables. ...
    (comp.lang.python)
  • Re: how can i large divide?
    ... Big-O notation is a representation of computational complexity, ... Let's say we have an Oalgorithm. ... We should all get in the habit of saying "a Thetaalgorithm" (if ...
    (comp.lang.c)
  • Adds and computational complexity
    ... algorithm, I stumbled across something called the Fast Euclidean ... while having a computational complexity of O/sample (N is the ... multiplications since we already know x*x' and xhas ... Does anyone know of an adaptive filtering algorithm with better ...
    (comp.soft-sys.matlab)
  • Re: how can i large divide?
    ... Big-O notation is a representation of computational complexity, ... Let's say we have an Oalgorithm. ... You can also do so without buying a faster computer. ...
    (comp.lang.c)
  • Re: how can i large divide?
    ... Big-O notation is a representation of computational complexity, ... Let's say we have an Oalgorithm. ... You can also do so without buying a faster computer. ...
    (comp.lang.c)