Prime Complexity

Computer Science Level 3

What is the runtime of the following pseudocode?

function(n)
     array x of n+1 booleans, all set to true
     x[0] = x[1] = false
     for i in 2 : n
         if x[i] = true
             j = 2 * i
             while j < n
                  x[j] = false
                  j += i

Details and Assumptions:

The question asks for the best upper bound to the runtime of the pseudocode, so if you think there are multiple correct answers, choose the answer which is the best upper bound among them.

O(n \log n)

O(\sqrt{n})

O(n^2)

O(n \log \log n)

1 solution

Spencer Whitehead
Feb 10, 2016

The key to solving this problem is to figure out what exactly it is doing!
We start with an array of booleans, all set to true. Then, any time we reach a number marked as true, we cross out all multiples of that number. So anything that is left is a number that isn't a multiple of any other number below it--a prime number.
So how long will this take?
The loop over i will execute n times, so all that remains is to find the complexity of the inner loop. We know that the inner loop will run about $\frac{N}{i}$ times. Since the inner loop is only running when i is prime by our reasoning above, we get a complexity of $O(n/2 + n/3 + n/5 \dots) = O(n(1/2 + 1/3 + 1/5 \dots)$ . Since the sum of all primes up to $n$ roughly equals $\log \log n$ , we get $O(n \log \log n)$ .

A seasoned computer science student may also notice that this is the Sieve of Eratosthenes, and have recognized its runtime. You can read more about it: sieve of eratosthenes .

Do note that $O(n^2)$ and $O(n\log n)$ are also correct answers, albeit not the best upper bounds. If we're asked for the best (tightest) upper bound out of the given options, then the answer is undoubtedly $O(n\log\log n)$ .

I have rephrased the problem to mention that the question asks for the best upper bound out of the given options. I hope the edit is to your liking. Thanks.

Prasun Biswas - 5 years, 4 months ago

Haha, of course! Good catch :)

Spencer Whitehead - 5 years, 4 months ago

Prime Complexity

1 solution

0 pending reports