0
$\begingroup$

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

$\endgroup$
  • $\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 '19 at 11:41
  • 1
    $\begingroup$ At least you should be able to write the number of operations as a sum. $\endgroup$ – gnasher729 Jul 29 '19 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 '19 at 12:51
  • 1
    $\begingroup$ Doesn't the Wikipedia page contain the answer? $\endgroup$ – xskxzr Aug 29 '19 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.

| cite | improve this answer | |
$\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 '19 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 '19 at 0:41
  • $\begingroup$ but that still does not tell why time complexity = O(n*log(log n)) ? $\endgroup$ – kevin Jul 31 '19 at 5:27
  • $\begingroup$ Paragraph 3 of my answer. You need to do a bit of work yourself. $\endgroup$ – gnasher729 Jul 31 '19 at 6:31
  • $\begingroup$ Why add 1/k for only the primes k with 2^m ≤ k < 2^(m+1) ? $\endgroup$ – kevin Jul 31 '19 at 6:46

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