recategorized by
454 views
0 votes
0 votes
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
recategorized by

Please log in or register to answer this question.

Related questions

2 votes
2 votes
1 answer
2
smartmeet asked Feb 7, 2017
881 views
A B-tree of order m is a tree which satisfies the following properties:Every node has at most m children.Every node (except root) has at least ⌈m/2⌉ children maximi...