gatebook mt2 qn 42

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

DOUBT: Why is option 3 false? Since it is given "bits[r] is supposed to equal 1 if and only if N is composite." so why cant we just do a direct search? If it is 0 its prime, otherwise composite? What is the problem in this?

Comments

me too got it wrong.

Answer 1

for ( int x = 2; x < N; x = x + 1 ) {
int y = x
while ( y < N ) {
bits[y] = 1
y = y + x
}
}

1. It needs O(n) extra space for storing bits[i] information.
2. For each value of x while loop will run N/x times.
   T(n) = N/2 + N/3 + N/4 ........+ 1 = O(NlogN)

3. For x = 2,3,5,7,11 .... (or any prime no ) below code makes bit[prime_no] = 1,
    i.e. for every x (irrespective of prime or composite) bit[x] becomes 1.
     
      //(for option 3, i am taking x value only as prime no ) and i am executing while loop just one time.

     For each prime x{
     int y = x                   // y is a prime no
     while ( y < N ) {      // True
     bits[y] = 1               //bit[prime_no] = 1
     y = y + x
    }}
   So statement 3 is false.