Consider the following C program segment:
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; }
Let $T(n)$ denote number of times the $for$ loop is executed by the program on input $n$. Which of the following is TRUE?
$T(n) = O(\sqrt{n}) \: \text{ and } T(n) = \Omega(\sqrt{n})$
$T(n) = O(\sqrt{n}) \: \text{ and } T(n) = \Omega(1)$
$T(n) = O(n) \: \text{ and } T(n) = \Omega(\sqrt{n})$
None of the above
Answer is option B.
Worst Case : $T(n) = \mathcal{O}(\sqrt{n})$
Best Case : When $n$ is an even number body of $for$ loop is executed only $1$ time (due to "$return \ 0$" inside if) which is irrespective of $n$. $\therefore T(n) = \Omega(1)$
@Tauhin_Gangwar , @arjun sir , @srestha :O Do the return 1 or 0 statement inside a loop make so much difference in execution of the code ? If so could you pls explain little bit detail How it is working ? ( What i knew is these numbers are used for exception handling purpose )
Actually question here difference between return 1, return 0, return -1.
we discussed here lot https://gateoverflow.in/95656/programming
still not satisfactory result.
Let T(n) denote number of times the for loop is executed by the program on input n.
Input n was sent to the function, but the function creates its own auto variable n which takes garbage value. The number of times the loop runs does not depend on the input n sent.
D. None of these