111

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?

Improve this question
2
  • 6
    I don't know about the rest (too mathy for my too sleepy brain right now), but the square root stems from the fact that if a number has no divisors less that its square root, it is prime. Also, I just learned that loglog(n) means there's a square root. Nice. Commented Apr 6, 2010 at 5:11
  • 15
    How does the loglog(n) being there mean there is a sqrt(n) somewhere? (@Martinho: Why do you say you "just learned this"?) The actual analysis does not involve any square roots! Commented Apr 22, 2010 at 22:48

5 Answers 5

Reset to default
140

  1. 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.)

  2. 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.

Improve this answer
Sign up to request clarification or add additional context in comments.

15 Comments

For one part of the problem, you are considering the asymptotic complexity. For the other part, you are considering amortized compexity. I'm confused.
@crisron What is the problem? It's not the case that "asymptotic complexity" and "amortized complexity" are two different kinds of the same thing. Amortization is just a technique for more carefully counting something, which can happen to be the asymptotic complexity.
All this while I used to think of them as different. Thanks for clarifying it.
@ShreevatsaR Why do we calculate the sum of harmonic series upto n terms. Shouldn't we calculate just upto sqrt(n) terms? Giving the answer as theta of n(loglogsqrt(n)) arithmetic operations? Also, wikipedia says that the space complexity is O(n). Shouldn't that be theta of n because we need an array of n elements in any case?
@s_123 :-) Θ is a Unicode character; I just copy-pasted it from somewhere else but you can also probably find a keyboard layout with which you can input this character. Also you may find my answer here helpful: What is the difference between O, Ω, and Θ?
|
8

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.

Improve this answer

2 Comments

this statement is true in itself, but has no bearing on the quoted statement which itself has no merit. Whether we start from p or p^2, the complexity is the same (with direct access arrays). SUM (1/p) {p<N} ~ log (log N) is the reason.
The optimization in this answer helped me fix a "time limit exceeded" error on leetcode :)
7
  1. The inner loop does n/i steps, where i is prime => the whole complexity is sum(n/i) = n * sum(1/i). According to prime harmonic series, the sum (1/i) where i is prime is log (log n). In total, O(n*log(log n)).
  2. I think the upper loop can be optimized by replacing n with sqrt(n) so overall time complexity will O(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;
        }
    }    
}
Improve this answer

1 Comment

no, replacing n with sqrt(n) makes it ~ n log log (sqrt n) which is still ~ n log log n. and isprime is absolutely the wrong name to use there.
1 
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)

Improve this answer

Comments

-2

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))))

Improve this answer

1 Comment

wrong. we mark all the way to the N: N/2 + N/3 + N/5 + N/7 + N/11 + ... = N (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...) ~ N log log (sqrt N) ~ N log log N.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.