220 views

Let $T(n)$ denote the number of times the for loop in below code is executed on any input $n$. What can be said about $T(n)$?

int iscompute(int n)
{
for (int i=2;i<=sqrt(n); i++)
if(n%i) == 0)
{
printf("not computed");
return 0;
}
return 1;
}
1. $T(n)= O(\sqrt n)$ and $T(n)= \Omega(\sqrt n)$
2. $T(n)= O(\sqrt n)$ and $T(n)= \Omega(1)$
3. $T(n)= O( n)$ and $T(n)= \Omega (\sqrt n)$
4. None

int iscompute(int n)
{
for (int i=2;i<=sqrt(n); i++)
if(n%i) == 0)
{
printf("not computed");
return 0;
}
return 1;
}


For loop will run sqrt(n) times at worst when $n$ is a prime number. if n is any even number then if condition becomes true in 1st iteration only. So it will terminate after that.This will result Constant best case complexity.