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
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 146 |
| 3 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Yes, it is possible. This blog post explains how and why it can be done.
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.
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.
I think what Whiplash99 wanted to prove was that the solution in geeksforgeeks is not O(n).
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.
Kuha can you explain it how o(N) is slower than O(NloglogN). we are not getting.
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.
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.
Constant factors can make an algorithm slower for all reasonable inputs, even though it would become faster as input size approaches infinity.
This is true. But for sieve to run in most languages, N can't be greater than 10^7.
Linear sieve has a few other advantages over the normal approach, which you can read about in the before mentioned post