# What is the time complexity of the piece of code given below

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


Here the loop executes for $\Theta (\sqrt{n})$ time . But my teacher said that it is not because the lower bound is $\omega (1)$ I was not able to understand why it so .

Q1] Could some of you explain which one of us is right justifying reason ?

Q2] What is the importance of " return 0 " ? What would have been the change if there had no " return 0 inside looping function ?

Q3] In general What is the meaning of return 0, 1, -1 in C programming language ? I have read this from stackoverflow but that didn't solve . Need little bit explanation

• Regarding Q3: Questions about programming languages are off-topic here. You might want to read a tutorial or a reference. If you wouldn't have a return 0 in the loop the function wouldn't behave as its name implies it should. It'd return 1 for all numbers. – adrianN Dec 23 '16 at 21:54

## 1 Answer

The loop executes at most $O(\sqrt n)$ times because i is incremented in every iteration of the loop. You claim that it is also executed at least $\Omega(\sqrt n)$ times. This is not true because it has an early exit (the return statement). For example for even numbers the function returns during the first iteration.

If you recall the definition of $\Omega$, we have $f(n) \in \Omega(g(n))$ if there is some constant $n_0$ such that for all $n>n_0$ we have $c*g(n) < f(n)$ for some constant $c$. By this definition the runtime of your program can't be $\Omega(\sqrt n)$ because the loop makes only one iteration for infinitely many inputs (that is, you can't find a suitable $n_0$).

You can of course restrict your analysis to the worst case ($n$ is a prime number). Then you are correct in saying that the runtime is $\Theta(\sqrt n)$. There is a question about the relation of $O$, $\Omega$, best and worst case in case you find this confusing.

• $\omega ( \sqrt{n} )$ is also possible right ? According to Cormen we take that function which is asymptotically closest . dont we ? Which made me think it is $\theta(\sqrt{n})$ What is wrong about my assumption ? – Pc_ Dec 22 '16 at 16:49
• Given function is definitely $\mathcal{0}(n)$ ie For some class of input the given function is $\Omega(1)$ and for some class of input the given function is $\Omega(\sqrt{n})$ And the function is asymptotically closest to $\Omega(\sqrt{n})$ Hence it is $\Theta(\sqrt{n})$ – Pc_ Dec 22 '16 at 16:55
• @AkhilNadhPC, The answer already explains what is wrong with that. I suggest you re-read it. See especially the sentence that starts "This is not true because..." "Asymptotically closest" is not the definition of $\omega$ nor $\Theta$. I suggest you look up their mathematical definition and take another look at it; they are precise mathematical terms with a specific definition, and in case of doubt, looking at the definition is the way to definitively resolve your doubt. – D.W. Dec 22 '16 at 17:03
• Got it i missed for all n0 > n – Pc_ Dec 22 '16 at 17:25
• For all even n, the loop iterates once and only once (except for n = 0 or n = 2, where it doesn't iterate at all). – gnasher729 Dec 23 '16 at 9:25