I have the following program:

Iterate x from 1 to N. Check to see if x is prime. If it is, add it to a list of primes.

The way I check to see if it is prime is iterating through the current list of primes, and seeing if they can divide x evenly.

What is the order analysis of this program? I don't think it is O(n^2), because the growing list of primes certainly doesn't increase at the rate of n. I don't it is O(nlog(n)), either.

How would I perform order analysis of the function?


You are using the naive methods of Primality testing. For a given n the number of primes < n is given by the prime counting function, which is approximately n/log(n). I'm not 100% sure of the complexity of this method as you generally will not need to divide by all primes < sqrt(n).

The slightly more sophisticated Sieve_of_Eratosthenes has complexity O(n log log n).

  • So, assuming I only check the primes less than sqrt(n), it would be O(n*log(n/log(n))? – Nathan Merrill Mar 29 '14 at 13:20
  • Yes you only need to check up to sqrt(n) as if its composite one of the factors must be less than this. Complexity may turn out to be better than this. For large n its more than likely it will not be prime so you don't need to do all n/log(n) divisions. – Salix alba Mar 29 '14 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.