greedycoder69's blog

By greedycoder69, history, 9 months ago, ,

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

 » 9 months ago, # |   0 Auto comment: topic has been updated by greedycoder69 (previous revision, new revision, compare).
 » 9 months ago, # |   +13 Yes, it is possible. This blog post explains how and why it can be done.
•  » » 9 months ago, # ^ |   0 Thanks.
 » 9 months ago, # | ← Rev. 12 →   +1 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 secondsRun them yourself and see if you don't believe me.
•  » » 9 months ago, # ^ |   0 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.
•  » » » 9 months ago, # ^ |   0 I think what Whiplash99 wanted to prove was that the solution in geeksforgeeks is not O(n).
•  » » » » 9 months ago, # ^ |   0 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.
•  » » » » » 9 months ago, # ^ |   0 kuha can you explain it how o(N) is slower than O(NloglogN). we are not getting.
•  » » » » » » 9 months ago, # ^ |   +6 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.
•  » » » 9 months ago, # ^ |   +4 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.
•  » » » 9 months ago, # ^ |   +1 Constant factors can make an algorithm slower for all reasonable inputs, even though it would become faster as input size approaches infinity.
•  » » » » 9 months ago, # ^ |   0 This is true. But for sieve to run in most languages, N can't be greater than 10^7.
•  » » » » » 9 months ago, # ^ |   -8 Linear sieve has a few other advantages over the normal approach, which you can read about in the before mentioned post
•  » » 9 months ago, # ^ |   0 yeah i timed both the algorithm you are right.