Mairson's Sieve Space Complexity
In the paper Some New Upper Bounds on the Generation of Prime Numbers, Mairson outlines the algorithm below
He also says that the algorithm must store a doubly linked list at a cost of 2N logN, resulting in an O(N logN) space complexity. However looking at this algorithm, it only stores 3 arrays of size O(N). Where does this log(N) term come from?
Solution
Mairson's paper is focused on the bit-complexity of computing the prime numbers up to N. So the space complexity of O(N) words is equivalent to O(N log N) bits, because the numbers stored in the words have O(N) magnitude, thus requiring O(log N) bits. (You'll notice a B subscript to the big O in his notation. B for Bit-complexity.)
- How do I print the two elements of an array and the subsequent sum of these elements? (Goldbachs Primes Question)
- Goldbach conjecture exercise (c)
- Problem in writing Goldbach conjecture program
- Python prime generator in one-line
- is_prime one liner in python
- Validate if input number is prime
- Segmented Sieve of Eratosthenes?
- Prime-k solution doesn’t go above certain number in c++
- Is there a way to find the approximate value of the nth prime?
- Factorizing a number in Python
- Determining if a number is prime
- Fastest prime test for small-ish numbers
- Java 8: streams and the Sieve of Eratosthenes
- Get prime numbers from a List using a Java stream
- Fastest way to list all primes below N
- How can I calculate this prime product faster with PARI/GP?
- Finding next prime number lands in an execution error (time limit exceeded)
- polynomial section of the AKS algorithm in Python
- Brent's cycle detection algorithm
- Iterating over a data structure with 51 million primes quickly
- Sieve of eratosthenes python script outputs non prime numbers
- Next prime number algorithm
- Miller-Rabin deterministic primality test (C)
- Implementing Miller-Rabin in C
- Pollard Rho factorization method implementation
- Wrote a program to print prime numbers, How do I make it better?
- Writing an isPrime function in Haskell
- Finding Primes, where did I got wrong?
- Why does my script stop execution after 33178210th iteration?
- Prime factorization of a factorial