Consider the following C code segment: int IsPrime(n) { int i,n;…

PYQ GATE 2007

Consider the following C code 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) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

  1. A.

    T(n) = O(√n) and T(n) = Ω(√n)

  2. B.

    T(n) = O(√n) and T(n) = Ω(1)

  3. C.

    T(n) = O(n) and T(n) = Ω(√n)

  4. D.

    None of the above

Attempted by 259 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…