Question

Cosider 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) denote the number of times the for loop is executed by the program on input n. Which of the following is true?

• A. None of these
• B. T(n) = O(n) and T(n) = $\Omega$ ($\sqrt{n}$)
• C. T(n) = O($\sqrt{n}$) and T(n) = $\Omega$ ($\sqrt{n}$)
• D. T(n) = O($\sqrt{n}$) and T(n) = $\Omega$ (1)

Answer 1

The correct option is D T(n) = O($\sqrt{n}$) and T(n) = $\Omega$ (1)

T(n) denote the number of times the for loop is execute by the program on input n.
T(n) = $\sqrt{n}$ + 1
When n = 1 then best case occurs so T(n) takes constant time i.e., T(n) = $\Omega$(1).
In worst case,
T(n) = $\sqrt{n}$ + 1
So T(n) = O($\sqrt{n}$).