Q51

MCQ2 marks, −0.5

Consider the following C program segment: int IsPrime (n) { int i, n; for (i=2; i<=sqrt(n);i++) if(n%i == 0) {printf("Not Prime \n"); return 0;} return 1; } Let $T(n)$ denote number of times the $for$ loop is executed by the program on input $n$ . Which of the following is TRUE?

(A)

$T(n) = O(\sqrt{n}) \: \text{ and } T(n) = \Omega(\sqrt{n})$

(B)

$T(n) = O(\sqrt{n}) \: \text{ and } T(n) = \Omega(1)$

(C)

$T(n) = O(n) \: \text{ and } T(n) = \Omega(\sqrt{n})$

(D)

None of the above

Loading…