what is the tightest lower bound of the below pseudo-code ?

Question

int isprime(int n )
{
for(int i=2;i<=sqrt(n) ; i++)
{
if(n%i==0)
{
not prime
}
}

Comments

for n=2 sqrt(2)= 1.414 , so 2 is greater than sqrt(n) hence condition evaluates to false so loop will not execute even once so how is it the lower bound for this code.

---

Why should the loop run for us to calculate the time complexity? Condition for the input should be given separately. If not assume a reasonable one- here even 1 is possible.

---

So sir then how do we actually calculate the min value of n for which the code runs atleast once in any general scenario.

Answer 1

I think tightest lower bound is  Ω(1) . 

if you input is say 2 or 3  then it will i<=sqrt(n) become false and exit .  and its worst case  O(n^0.5)

this prog will be more efficient if there is break statement in the if part  . 

int isprime(int n )
{
for(int i=2;i<=sqrt(n) ; i++)
{
if(n%i==0)
{
not prime
break ;

}
}

Comments

Can u plz tell how many times will the if statement return true ,it will do so when n=i,2i,3i and so on so now since i runs for sqrt n times so then how many times will if statement return true ?