greedycoder69's blog

By greedycoder69, history, 3 months 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

 
 
 
 

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by greedycoder69 (previous revision, new revision, compare).

»
3 months 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.

»
3 months 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.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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).

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          3 months 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.

          • »
            »
            »
            »
            »
            »
            3 months 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.

    • »
      »
      »
      3 months 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.

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah i timed both the algorithm you are right.