Re: The computational complexity of the Sieve of Eratosthenes

Juha Nieminen <nospam@xxxxxxxxxxxxxx> writes:

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

Yes!

<snip>
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?

Hmm... This: http://ecommons.library.cornell.edu/handle/1813/6313 is
the closest match that I can find to a publicly available[1] version
the Pritchard paper cited in the article. It is complex and hard to
read due, in part, to the typewriter format, but it may provide the
missing links.

[1] I don't have access to a good library anymore and I am constantly
frustrated that journals feel they must protect their "back
catalogue". What would they loose if all papers older than say 10
or 15 years, were made available? Libraries would still need
subscribe... Just a thought.

--
Ben.
.

Relevant Pages

  • Re: FUD about CGD and GBDE
    ... >government has approved the use of AES with 256 bit keys for very ... that stress on the algorithm and maintain 256 bits of margin. ... I don't seriously think that either of CGD or GBDE will be broken ... The first reason is that it adds complexity. ...
    (freebsd-hackers)
  • Re: Hooray: the Church of Scotland shows the way
    ... If you are simply pointing out the limitations of algorithmic machines then I agree completely. ... any Turing machine could print out the solution to a non-computable problem if that solution were part of the machine's algorithm. ... Given the complexity of the universe it doesn't seem unlikely that the solutions to all manner of non-computable problems have been physically realised in some form and lie there waiting for us to latch on to them somehow. ... Whilst it's true that fundamental physics are essentially algorithmic in nature, ...
    (uk.religion.christian)
  • Re: Predicting the Future and Kolmogorov Complexity
    ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ... cannot be algorithmically random. ...
    (talk.origins)
  • Re: Intro to Programming w/ Machine Language
    ... > Based upon your previous posts, I found this pretty surprising. ... > If n is sufficiently large, the Ocomplexity obviously matters. ... where's the Oor Oalgorithm that's ... people use in the good old "assembly vs. HLL" religous wars. ...
    (alt.lang.asm)
  • Re: Benchmarks
    ... something about time or space complexity. ... f is often the worst case runtime of an algorithm ... you can use Big-O notation also to say something ... You talk about the big-O notation as some kind of generic function ...
    (comp.lang.c)