Gatebook_Mocktest2(DS)

Question

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

Answer 1

i have implemented this algo(Sieve of Eratosthenes) on Codechef.

but i am conform that I and III are correct.

I==> array is required of size n so we can fill with 0 and 1 for dectacting number is prime or not

III==>.after execution algo we can find in O(1) that number is prime or not.

if(array[x]==1)

composite number

else

Prime number

the complexity is O(nloglogn)

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity

but i am some confused with the code written in question and language of the question.

in question written that ->bits[r] is supposed to equal 1 if and only if N is composite

but bits[2]=1 and 2 is prime not composite.

Comments

bits[2] would not be 1 becoz 2 is not composite..bits[2]=0;

and complexity is O(n) possible...see this http://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/