in Algorithms
220 views
4 votes
4 votes

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
in Algorithms
by
220 views

1 Answer

6 votes
6 votes
Best answer
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.

selected by
Answer:

Related questions