##### 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) = (sqrt(n)) (B) T(n) = O(sqrt(n)) and T(n) = (1) (C) T(n) = O(n) and T(n) = (sqrt(n)) (D) None of the above I think ans is A) , in madeeasy previous year book and geeksfogeeks shows B,Help me out
shivani
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
19 Aug 2017 03:48 pm

thank you i didn't see that return 0;