Consider the following C code segment: int IsPrime(n) { int i,n;…
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?
- A.
T(n) = O(√n) and T(n) = Ω(√n)
- B.
T(n) = O(√n) and T(n) = Ω(1)
- C.
T(n) = O(n) and T(n) = Ω(√n)
- D.
None of the above
Attempted by 135 students.
Show answer & explanation
Correct answer: B
Answer: The correct statement is T(n) = O(sqrt(n)) and T(n) = Ω(1).
Reason:
Upper bound (O(sqrt(n))): In the worst case (for example when n is prime) the loop variable i runs from 2 up to floor(sqrt(n)), so the number of iterations is proportional to sqrt(n). Therefore T(n) = O(sqrt(n)).
Lower bound (Ω(1)): There exist inputs where a small divisor is found immediately, e.g., any even n is divisible by 2, so the loop executes just one iteration and returns. Hence T(n) can be constant, so T(n) = Ω(1).
Conclusion: Since the maximum number of iterations grows like sqrt(n) but some inputs require only a constant number of iterations, the correct asymptotic bounds are O(sqrt(n)) and Ω(1).
Why the other statements are wrong:
Any claim that T(n) = Ω(sqrt(n)) is false because some inputs make the loop stop after a constant number of iterations.
Claiming T(n) = O(n) is not incorrect but is weaker than the true upper bound O(sqrt(n)); mixing that with an incorrect lower bound does not yield a correct statement.