0
$\begingroup$

Wikipedia states that the Sieve of Eratosthenes runs in time $O(n\log\log n)$. Why is that so?

$\endgroup$

closed as unclear what you're asking by xskxzr, dkaeae, Evil, Yuval Filmus, Juho Sep 13 at 9:50

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Follow the algorithm and see how many operations it will perform. It is "a direct consequence of the fact that the prime harmonic series asymptotically approaches log log n $\endgroup$ – gnasher729 Jul 29 at 11:41
  • 1
    $\begingroup$ At least you should be able to write the number of operations as a sum. $\endgroup$ – gnasher729 Jul 29 at 12:00
  • $\begingroup$ @gnasher729 Why prime harmonic series asymptotically approaches log log n ? I have read the proof on that link, but I am still confused. $\endgroup$ – kevin Jul 29 at 12:51
  • 1
    $\begingroup$ Doesn't the Wikipedia page contain the answer? $\endgroup$ – xskxzr Aug 29 at 11:45
1
$\begingroup$

Write a sum for the number of operations of removing multiples of primes. How many operations to remove all multiples of 103 for example from an array of n bits? How many operations to remove all multiples of a prime number p? So you get a sum.

Then you need to know what the sum 1/1 + 1/2 + 1/3 + ... + 1/n is (roughly) and importantly why. You see that by adding 1/1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + (1/8 + 1/9 ... + 1/15) + ... and there is an obvious upper bound.

Now instead of adding 1/k for $2^m ≤ k < 2^{m+1}$ you add 1/k for only the primes k with $2^m ≤ k < 2^{m+1}$. How many are there? What sum do you get now? And then you have a sum that looks almost exactly like the one you started with and gives you the result.

$\endgroup$
  • $\begingroup$ by adding 1/1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + (1/8 + 1/9 ... + 1/15) + ... and there is an obvious upper bound. <-- Huh? How obvious is that ? $\endgroup$ – kevin Jul 30 at 3:20
  • $\begingroup$ The first is 1. The second is two numbers <= 1/2 therefore <= 1. The third is four numbers <= 1/4 therefore <= 1. The next is 8 numbers <= 1/8 therefore <= 1. $\endgroup$ – gnasher729 Jul 31 at 0:41
  • $\begingroup$ but that still does not tell why time complexity = O(n*log(log n)) ? $\endgroup$ – kevin Jul 31 at 5:27
  • $\begingroup$ Paragraph 3 of my answer. You need to do a bit of work yourself. $\endgroup$ – gnasher729 Jul 31 at 6:31
  • $\begingroup$ Why add 1/k for only the primes k with 2^m ≤ k < 2^(m+1) ? $\endgroup$ – kevin Jul 31 at 6:46

Not the answer you're looking for? Browse other questions tagged or ask your own question.