Find the time complexity for the following C code segment.

GATE | GATE-CS-2007 | Question 51

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?
(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 the above

I think ans is A) , in madeeasy previous year book and geeksfogeeks shows B,Help me out

2Comments
shivani @shivani1234
19 Aug 2017 12:40 pm

While checking whether number is prime or not , we go from 1 to √n , until we get the no. divisible or until no. till √n gets exhausted.

Ex. for 169 , we check from 1 to 13
while for 150, we check till 2 only.

So, in worst case , its O(√n) and in best case its omega(1)

Rahul @rahul55523
19 Aug 2017 03:48 pm

thank you i didn't see that return 0;