The intended purpose of this code is to precompute all the primes less than N. When it is finished executing, for r ∈ [2, N), bits[r] is supposed to equal 1 if and only if N is composite. Assume that the bits array is initialized to all zeroes.
for ( int x = 2; x < N; x = x + 1 ) {
int y = x
while ( y < N ) {
bits[y] = 1
y = y + x
}
}
Which of the following statements is/are true?
I. The algorithm requires O(N) temporary space.
II. The algorithm demonstrates an asymptotic algorithmic complexity of O(N ln(N)).
III. After the initialization shown above, it is possible to determine in O(1) time whether a natural number n < N is prime.
(A) I only
(B) I and II only
(C) II and III only
(D) I, II, and III