GATE Overflow | Algorithms | Test 1 | Question: 20

Question

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;
}

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

Answer 1

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.