"return 0" acts as an exit condition. Basically, "return 0" means "success" — hence, no need to proceed further.
int IsPrime (n)
{
int i, n;
/* Take n = 100 */
for (i=2; i<=sqrt(n);i++)
/* Would run O(√100) times, normally. */
if(n%i == 0)
/* True, so enter "if". */
{printf("Not Prime \n"); return 0;}
/* return 0 means, "Success!
This number is successfully determined to be non-prime,
hence no need to go on." So, we exit for-loop */
return 1;
}
Hence, in the best case, we'll encounter "return 0" at the first iteration, so Ω(1).
In the worst case, it'll go from i = 2, to i = √n — never encountering "return 0" — means O(√n) times.
So, Option B.
If the code was like this:-
int IsPrime (n)
{
int i, n;
for (i=2; i<=sqrt(n);i++)
if(n%i == 0)
{printf("Not Prime \n");}
return 1;
}
Then, there's no early exit condition (return 0). Then, Option A would be the answer, because the only way for-loop would be broken out of, is to iterate completely.