greedycoder69's blog

Can Sieve of Eratosthenes takes O(N)?
By greedycoder69, history, 6 years ago, In English

hey we all know that Sieve of Eratosthenes takes O(N log (log N)) but in one of the article of geeksforgeeks Sieve of Eratosthenes takes O(N) time and they have also provided explanation source code. Here is the link. is it possible in O(N) if yes then explain

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Yes, it is possible. This blog post explains how and why it can be done.

→ Reply
»
6 years ago, # |
← Rev. 12   Vote: I like it +1 Vote: I do not like it

I timed both the algorithms. The O(N) solution of GeeksForGeeks is slower than the O(NloglogN) algorithm in practice. I took N=10^7, N=10^6 and N=10^5. In all the cases, the O(NloglogN) algorithm ran faster. I ran them in Java.

Proof: O(NloglogN) for N=10^7: approx 0.07 seconds O(N) for N=10^7: approx 0.15 seconds

Run them yourself and see if you don't believe me.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ok thanks but i am not getting one thing how it can be possible O(NloglogN) is faster than O(N) because when loglogN multiply with N obviously it increases time.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think what Whiplash99 wanted to prove was that the solution in geeksforgeeks is not O(n).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Not only the one given in GeeksForGeeks, but also the one given in the link by Kuha. You can see the links I gave above as a proof. I ran both of them 5-6 times and these were the approximate timings I got each time.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Kuha can you explain it how o(N) is slower than O(NloglogN). we are not getting.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            That's probably caused by the constant factors. I think the main reason is that for the computer for (j = i * i; j <= N; j += i) a[j] = false; loop is more predictable than the loop of O(n) sieve.

            But yeah, the O(n) sieve has some advantages for multiplicative functions, especially if they're more complex ones.

            → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Maybe this is the reason:

      The O(N) sieve uses an extra array/vector to store the prime numbers. When we are dealing with large N like 10^7 or 10^6, this may affect the running time of the program.

      This is just a logical guess. I think more experienced coders may be able to explain the reason for this.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Constant factors can make an algorithm slower for all reasonable inputs, even though it would become faster as input size approaches infinity.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is true. But for sieve to run in most languages, N can't be greater than 10^7.

        → Reply