NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 8

Question

Consider the following C code segment:

int Ls Prime(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 the 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})$ and $T(n) = \Omega (\sqrt{n})$
• B. $T(n) = O(\sqrt{n})$ and $T(n) = \Omega (1)$
• C. $T(n) = O(n)$ and $T(n) = \Omega (\sqrt{n})$
• D. None of these

Answer 1

option b

in best case  if cond satisfy 1 time and return  

 

in wrost case  root(n)  time loop will itetrate

Answer 2

Ans: B)

References: https://softwareengineering.stackexchange.com/a/310490/321927

Answer 3

Option B) is the answer , Best case complexity –  O(1)

                                        Worst case complexity – O(n^1/2)