Time complexity of Sieve of Eratosthenes algorithm
AlgorithmPerformanceTime ComplexitySieve of-EratosthenesAlgorithm Problem Overview
From Wikipedia:
> The complexity of the algorithm is
> O(n(logn)(loglogn))
bit operations.
How do you arrive at that?
That the complexity includes the loglogn
term tells me that there is a sqrt(n)
somewhere.
Suppose I am running the sieve on the first 100 numbers (n = 100
), assuming that marking the numbers as composite takes constant time (array implementation), the number of times we use mark_composite()
would be something like
n/2 + n/3 + n/5 + n/7 + ... + n/97 = O(n^2)
And to find the next prime number (for example to jump to 7
after crossing out all the numbers that are multiples of 5
), the number of operations would be O(n)
.
So, the complexity would be O(n^3)
. Do you agree?
Algorithm Solutions
Solution 1 - Algorithm
-
Your n/2 + n/3 + n/5 + … n/97 is not O(n), because the number of terms is not constant. [Edit after your edit: O(n2) is too loose an upper bound.] A loose upper-bound is n(1+1/2+1/3+1/4+1/5+1/6+…1/n) (sum of reciprocals of all numbers up to n), which is O(n log n): see Harmonic number. A more proper upper-bound is n(1/2 + 1/3 + 1/5 + 1/7 + …), that is sum of reciprocals of primes up to n, which is O(n log log n). (See here or here.)
-
The "find the next prime number" bit is only O(n) overall, amortized — you will move ahead to find the next number only n times in total, not per step. So this whole part of the algorithm takes only O(n).
So using these two you get an upper bound of O(n log log n) + O(n) = O(n log log n) arithmetic operations. If you count bit operations, since you're dealing with numbers up to n, they have about log n bits, which is where the factor of log n comes in, giving O(n log n log log n) bit operations.
Solution 2 - Algorithm
> That the complexity includes the loglogn term tells me that there is a sqrt(n) somewhere.
Keep in mind that when you find a prime number P
while sieving, you don't start crossing off numbers at your current position + P
; you actually start crossing off numbers at P^2
. All multiples of P
less than P^2
will have been crossed off by previous prime numbers.
Solution 3 - Algorithm
- The inner loop does
n/i
steps, wherei
is prime => the whole complexity issum(n/i) = n * sum(1/i)
. According to prime harmonic series, thesum (1/i)
wherei
is prime islog (log n)
. In total,O(n*log(log n))
. - I think the upper loop can be optimized by replacing
n
withsqrt(n)
so overall time complexity willO(sqrt(n)loglog(n))
:
void isPrime(int n){
int prime[n],i,j,count1=0;
for(i=0; i < n; i++){
prime[i] = 1;
}
prime[0] = prime[1] = 0;
for(i=2; i <= n; i++){
if(prime[i] == 1){
printf("%d ",i);
for(j=2; (i*j) <= n; j++)
prime[i*j] = 0;
}
}
}
Solution 4 - Algorithm
int n = 100;
int[] arr = new int[n+1];
for(int i=2;i<Math.sqrt(n)+1;i++) {
if(arr[i] == 0) {
int maxJ = (n/i) + 1;
for(int j=2;j<maxJ;j++)
{
arr[i*j]= 1;
}
}
}
for(int i=2;i<=n;i++) {
if(arr[i]==0) {
System.out.println(i);
}
}
For all i>2, Ti = sqrt(i) * (n/i) => Tk = sqrt(k) * (n/k) => Tk = n/sqrt(k)
Loop stops when k=sqrt(n) => n[ 1/sqrt(2) + 1/sqrt(3) + ...] = n * log(log(n)) => O(nloglogn)
Solution 5 - Algorithm
see take the above explanation the inner loop is harmonic sum of all prime numbers up to sqrt(n). So, the actual complexity of is O(sqrt(n)*log(log(sqrt(n))))