3.3k views

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?

1. $T(n) = O(\sqrt{n}) \: \text{ and } T(n) = \Omega(\sqrt{n})$

2. $T(n) = O(\sqrt{n}) \: \text{ and } T(n) = \Omega(1)$

3. $T(n) = O(n) \: \text{ and } T(n) = \Omega(\sqrt{n})$

4. None of the above

edited | 3.3k views

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)$

edited
0
@Tauhin

Scope of for() loop is entirely if () condition, which returns 0.

and it's else portion returning 1.

So, while returning 1 , it is going inside for loop again.

and when returning 0, then it breaks for loop and terminates.

rt?
0
na na... return 1... is normal...execution..as compiler executes step by step....u cannot consider it "else " part... bcoz if u consider it else...then it b inside for loop....i m still not very clear
+1
:O "return 1" is not part of "if" or "else" or even the for loop. Hence it does not affect the answer here. There is no implicit "else" in C or any language I know.
0
ok..yes u right sir..
0

@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 )

+2
Take n= any even number

any loop or condition only evaluated one time

And returning 0 , means go outside all loops

So,$\Omega (1)$

it is also true for $\Omega (n)$

i.e. why ans is $\Omega (1)$
0

Actually question here difference between return 1, return 0, return -1.

we discussed here lot https://gateoverflow.in/95656/programming

still not satisfactory result.

0
@arjun sir, good clarification sir
0
Shouldn't it be for 17 .. we check for 2,3,4 ? Why is it written , for 17 check for ... 2,3,5 ?
0
Can you explain both the cases by taking some value of n....

Let T(n) denote number of times the for loop is executed by the program on input n.

int i, 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

0
If we check for N= 2 the n%2== 0 it will be printed that not prime..

But I think 2 is prime...
It is not checking for 2 right?

1
2